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 |
Keywords
- Cardinality constraint
- Integral polytope
- Transportation problem with market choice
Fingerprint Dive into the research topics of 'On a cardinality-constrained transportation problem with market choice'. Together they form a unique fingerprint.
Cite this
Walter, M., Damci-Kurt, P., Dey, S. S., & Küçükyavuz, S. (2016). On a cardinality-constrained transportation problem with market choice. Operations research letters, 44(2), 170-173. https://doi.org/10.1016/j.orl.2015.12.001