On a cardinality-constrained transportation problem with market choice

Matthias Walter, Pelin Damci-Kurt, Santanu S. Dey*, Simge Kucukyavuz

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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 (US)
Pages (from-to)170-173
Number of pages4
JournalOperations Research Letters
Volume44
Issue number2
DOIs
StatePublished - Mar 2016

Keywords

  • Cardinality constraint
  • Integral polytope
  • Transportation problem with market choice

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On a cardinality-constrained transportation problem with market choice'. Together they form a unique fingerprint.

Cite this