Advanced search

The transportation problem with exclusionary side constraints

Author
Organization
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).
Keywords
Transportation problem, ALGORITHMS, Exclusionary side constraints, Complexity

Citation

Please use this url to cite or link to this publication:

Chicago
Goossens, Dries, and Frits Spieksma. 2009. “The Transportation Problem with Exclusionary Side Constraints.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 7 (1): 51–60.
APA
Goossens, Dries, & Spieksma, F. (2009). The transportation problem with exclusionary side constraints. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 7(1), 51–60.
Vancouver
1.
Goossens D, Spieksma F. The transportation problem with exclusionary side constraints. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH. 2009;7(1):51–60.
MLA
Goossens, Dries, and Frits Spieksma. “The Transportation Problem with Exclusionary Side Constraints.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 7.1 (2009): 51–60. Print.
@article{5638041,
  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).},
  author       = {Goossens, Dries and Spieksma, Frits},
  issn         = {1619-4500},
  journal      = {4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH},
  keywords     = {Transportation problem,ALGORITHMS,Exclusionary side constraints,Complexity},
  language     = {eng},
  number       = {1},
  pages        = {51--60},
  title        = {The transportation problem with exclusionary side constraints},
  url          = {http://dx.doi.org/10.1007/s10288-007-0067-z},
  volume       = {7},
  year         = {2009},
}

Altmetric
View in Altmetric
Web of Science
Times cited: