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 journalArticleAcademicpeer-review

5 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 languageEnglish
Pages (from-to)170-173
Number of pages4
JournalOperations research letters
Volume44
Issue number2
Early online date31 Dec 2015
DOIs
Publication statusPublished - 1 Mar 2016
Externally publishedYes

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