Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloThe Red-Blue transportation problem
Anno di pubblicazione2014
Formato
  • Elettronico
  • Cartaceo
Autore/iVancroonenburg W.; Della Croce F.; Goossens D.; Spieksma F.C.R.
Affiliazioni autoriKU Leuven, Department of Computer Science, CODeS and IMinds-ITEC, Gebroeders De Smetstraat 1, BE-9000 Gent, Belgium; Politecnico di Torino, D.A.I., Torino, Italy; CNR, IEIIT, Torino, Italy; Ghent University, Faculty of Economics and Business Administration, Tweekerkenstraat 2, BE-9000 Gent, Belgium; KU Leuven, Faculty of Economics and Business, ORSTAT, Naamsestraat 69, BE-3000 Leuven, Belgium
Autori CNR e affiliazioni
  • FEDERICO DELLA CROCE DI DOJOLA
Lingua/e
  • inglese
AbstractThis paper considers the Red-Blue Transportation Problem (Red-Blue TP), a generalization of the transportation problem where supply nodes are partitioned into two sets and so-called exclusionary constraints are imposed. We encountered a special case of this problem in a hospital context, where patients need to be assigned to rooms. We establish the problem's complexity, and we compare two integer programming formulations. Furthermore, a maximization variant of Red-Blue TP is presented, for which we propose a constant-factor approximation algorithm. We conclude with a computational study on the performance of the integer programming formulations and the approximation algorithms, by varying the problem size, the partitioning of the supply nodes, and the density of the problem. © 2014 Elsevier B.V. All rights reserved.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da814
Pagine a823
Pagine totali-
RivistaEuropean journal of operational research
Attiva dal 1977
Editore: Elsevier - Amsterdam
Paese di pubblicazione: Paesi Bassi
Lingua: inglese
ISSN: 0377-2217
Titolo chiave: European journal of operational research
Titolo proprio: European journal of operational research.
Titolo abbreviato: Eur. J. oper. res.
Numero volume della rivista237
Fascicolo della rivista3
DOI10.1016/j.ejor.2014.02.055
Verificato da refereeSì: Internazionale
Stato della pubblicazionePublished version
Indicizzazione (in banche dati controllate)
  • Scopus (Codice:2-s2.0-84899968896)
Parole chiaveApproximation, Complexity, Exclusionary constraints, Integer programming, Transportation problem
Link (URL, URI)http://www.scopus.com/inward/record.url?eid=2-s2.0-84899968896&partnerID=q2rCbXpz
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR
    Progetti Europei-
    Allegati