On a cardinality-constrained transportation problem with market choice

Matthias Walter; Pelin Damci-Kurt; Santanu S. Dey; Simge Küçükyavuz

doi:10.1016/j.orl.2015.12.001

On a cardinality-constrained transportation problem with market choice

Matthias Walter, Pelin Damci-Kurt, Santanu S. Dey^*, Simge Küçükyavuz

^*Corresponding author for this work

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

6 Citations (Scopus)

Abstract

It is well-known that the intersection of the matching polytope with a cardinality constraint is integral (Schrijver, 2003) [8]. In this note, we prove a similar result for the polytope corresponding to the transportation problem with market choice (TPMC) (introduced in DamcI-Kurt et al. (2015)) when the demands are in the set {1,2}. This result generalizes the result regarding the matching polytope. The result in this note implies that some special classes of minimum weight perfect matching problem with a cardinality constraint on a subset of edges can be solved in polynomial time.

Original language	English
Pages (from-to)	170-173
Number of pages	4
Journal	Operations research letters
Volume	44
Issue number	2
Early online date	31 Dec 2015
DOIs	https://doi.org/10.1016/j.orl.2015.12.001
Publication status	Published - 1 Mar 2016
Externally published	Yes

Keywords

Cardinality constraint
Integral polytope
Transportation problem with market choice

Access to Document

10.1016/j.orl.2015.12.001

Cite this

@article{e1bd07a4a08d414c81bfb8ea801d1150,

title = "On a cardinality-constrained transportation problem with market choice",

abstract = "It is well-known that the intersection of the matching polytope with a cardinality constraint is integral (Schrijver, 2003) [8]. In this note, we prove a similar result for the polytope corresponding to the transportation problem with market choice (TPMC) (introduced in DamcI-Kurt et al. (2015)) when the demands are in the set {1,2}. This result generalizes the result regarding the matching polytope. The result in this note implies that some special classes of minimum weight perfect matching problem with a cardinality constraint on a subset of edges can be solved in polynomial time.",

keywords = "Cardinality constraint, Integral polytope, Transportation problem with market choice",

author = "Matthias Walter and Pelin Damci-Kurt and Dey, {Santanu S.} and Simge K{\"u}{\c c}{\"u}kyavuz",

year = "2016",

month = mar,

day = "1",

doi = "10.1016/j.orl.2015.12.001",

language = "English",

volume = "44",

pages = "170--173",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - On a cardinality-constrained transportation problem with market choice

AU - Walter, Matthias

AU - Damci-Kurt, Pelin

AU - Dey, Santanu S.

AU - Küçükyavuz, Simge

PY - 2016/3/1

Y1 - 2016/3/1

N2 - It is well-known that the intersection of the matching polytope with a cardinality constraint is integral (Schrijver, 2003) [8]. In this note, we prove a similar result for the polytope corresponding to the transportation problem with market choice (TPMC) (introduced in DamcI-Kurt et al. (2015)) when the demands are in the set {1,2}. This result generalizes the result regarding the matching polytope. The result in this note implies that some special classes of minimum weight perfect matching problem with a cardinality constraint on a subset of edges can be solved in polynomial time.

AB - It is well-known that the intersection of the matching polytope with a cardinality constraint is integral (Schrijver, 2003) [8]. In this note, we prove a similar result for the polytope corresponding to the transportation problem with market choice (TPMC) (introduced in DamcI-Kurt et al. (2015)) when the demands are in the set {1,2}. This result generalizes the result regarding the matching polytope. The result in this note implies that some special classes of minimum weight perfect matching problem with a cardinality constraint on a subset of edges can be solved in polynomial time.

KW - Cardinality constraint

KW - Integral polytope

KW - Transportation problem with market choice

UR - http://www.scopus.com/inward/record.url?scp=84954473462&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2015.12.001

DO - 10.1016/j.orl.2015.12.001

M3 - Article

AN - SCOPUS:84954473462

SN - 0167-6377

VL - 44

SP - 170

EP - 173

JO - Operations research letters

JF - Operations research letters

IS - 2

ER -

On a cardinality-constrained transportation problem with market choice

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this