文摘
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 Damcı-Kurt et al. (2015)) when the demands are in the set class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0167637715001601&_mathId=si1.gif&_user=111111111&_pii=S0167637715001601&_rdoc=1&_issn=01676377&md5=b9b14accfaf5b5672ab2dea98aac04c7" title="Click to view the MathML source">{1,2}class="mathContainer hidden">class="mathCode">. 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.