TY - JOUR
T1 - On a cardinality-constrained transportation problem with market choice
AU - Walter, Matthias
AU - Damci-Kurt, Pelin
AU - Dey, Santanu S.
AU - Kucukyavuz, Simge
N1 - Funding Information:
Pelin Damcı-Kurt and Simge Küçükyavuz are supported, in part, by NSF-CMMI grant 1055668 . Santanu S. Dey gratefully acknowledges the support of the Air Force Office of Scientific Research grant FA9550-12-1-0154 .
Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2016/3
Y1 - 2016/3
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
UR - http://www.scopus.com/inward/citedby.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 -