The transportation problem with exclusionary side constraints

D.R. Goossens, F.C.R. Spieksma

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)

Abstract

We consider the so-called Transportation Problem with Exclusionary Side Constraints (TPESC), which is a generalization of the ordinary transportation problem. We confirm that the TPESC is NP-hard, and we analyze the complexity of different special cases. For instance, we show that in case of a bounded number of suppliers, a pseudo-polynomial time algorithm exists, whereas the case of two demand nodes is already hard to approximate within a constant factor (unless P = NP).
Original languageEnglish
Pages (from-to)51-60
Journal4OR : A Quarterly Journal of Operations Research
Volume7
Issue number1
DOIs
Publication statusPublished - Mar 2009
Externally publishedYes

Keywords

  • Transportation problem
  • Exclusionary side constraints
  • Complexity

Fingerprint

Dive into the research topics of 'The transportation problem with exclusionary side constraints'. Together they form a unique fingerprint.

Cite this