The transportation problem with exclusionary side constraints

D.R. Goossens; F.C.R. Spieksma

doi:10.1007/s10288-007-0067-z

The transportation problem with exclusionary side constraints

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

Research output: Contribution to journal › Article › Academic › peer-review

18 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 language	English
Pages (from-to)	51-60
Journal	4OR : A Quarterly Journal of Operations Research
Volume	7
Issue number	1
DOIs	https://doi.org/10.1007/s10288-007-0067-z
Publication status	Published - Mar 2009
Externally published	Yes

Keywords

Transportation problem
Exclusionary side constraints
Complexity

Access to Document

10.1007/s10288-007-0067-z

Cite this

@article{97effcf6ef9f4580ace31a77989f272d,

title = "The transportation problem with exclusionary side constraints",

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, Exclusionary side constraints, Complexity",

author = "D.R. Goossens and F.C.R. Spieksma",

year = "2009",

month = mar,

doi = "10.1007/s10288-007-0067-z",

language = "English",

volume = "7",

pages = "51--60",

journal = "4OR : A Quarterly Journal of Operations Research",

issn = "1619-4500",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - The transportation problem with exclusionary side constraints

AU - Goossens, D.R.

AU - Spieksma, F.C.R.

PY - 2009/3

Y1 - 2009/3

N2 - 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).

AB - 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).

KW - Transportation problem

KW - Exclusionary side constraints

KW - Complexity

U2 - 10.1007/s10288-007-0067-z

DO - 10.1007/s10288-007-0067-z

M3 - Article

SN - 1619-4500

VL - 7

SP - 51

EP - 60

JO - 4OR : A Quarterly Journal of Operations Research

JF - 4OR : A Quarterly Journal of Operations Research

IS - 1

ER -

The transportation problem with exclusionary side constraints

Abstract

Keywords

Access to Document

Fingerprint

Cite this