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 | |
| Publication status | Published - 1 Mar 2016 |
| Externally published | Yes |
Fingerprint
Keywords
- Cardinality constraint
- Integral polytope
- Transportation problem with market choice
Cite this
}
On a cardinality-constrained transportation problem with market choice. / Walter, Matthias; Damci-Kurt, Pelin; Dey, Santanu S.; Küçükyavuz, Simge.
In: Operations research letters, Vol. 44, No. 2, 01.03.2016, p. 170-173.Research output: Contribution to journal › Article › Academic › peer-review
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
VL - 44
SP - 170
EP - 173
JO - Operations research letters
JF - Operations research letters
SN - 0167-6377
IS - 2
ER -