A TDI description of restricted 2-matching polytopes

Gyula Pap


We give a TDI description for a class of polytopes which corresponds to a restricted 2-matching problem. The perfect matching polytope, triangle-free perfect 2-matching polytope and relaxations of the traveling salesman polytope are members of this class. For a class of restrictions G. Cornuéjols, D. Hartvigsen and W.R. Pulleyblank have shown that the unweighted problem is tractable; here we show that the weighted problems for these classes are also tractable.

Bibtex entry:

AUTHOR = {Pap, Gyula},
TITLE = {A TDI description of restricted 2-matching polytopes},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-15}

Last modification: 29.12.2020. Please email your comments to Tamás Király!