TR-2004-15

A TDI description of restricted 2-matching polytopes

Gyula Pap



Abstract

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:

@techreport{egres-04-15,
AUTHOR = {Pap, Gyula},
TITLE = {A TDI description of restricted 2-matching polytopes},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-15}
}


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