On a cardinality-constrained transportation problem with market choice

Matthias Walter, Pelin Damci-Kurt, Santanu S. Dey, Simge Küçükyavuz

Research output: Contribution to journalArticleAcademicpeer-review

3 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

Fingerprint

Transportation Problem
Set theory
Cardinality
Polytope
Polynomials
Cardinality Constraints
Perfect Matching
Matching Problem
Polynomial time
Intersection
Imply
Generalise
Subset
Market
Transportation problem
Integral
Matching problem

Keywords

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

Cite this

Walter, Matthias ; Damci-Kurt, Pelin ; Dey, Santanu S. ; Küçükyavuz, Simge. / On a cardinality-constrained transportation problem with market choice. In: Operations research letters. 2016 ; Vol. 44, No. 2. pp. 170-173.
@article{e1bd07a4a08d414c81bfb8ea801d1150,
title = "On a cardinality-constrained transportation problem with market choice",
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.",
keywords = "Cardinality constraint, Integral polytope, Transportation problem with market choice",
author = "Matthias Walter and Pelin Damci-Kurt and Dey, {Santanu S.} and Simge K{\"u}{\cc}{\"u}kyavuz",
year = "2016",
month = "3",
day = "1",
doi = "10.1016/j.orl.2015.12.001",
language = "English",
volume = "44",
pages = "170--173",
journal = "Operations research letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "2",

}

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