A new bound for the ratio between the 2-matching problem and its linear programming relaxation

DOI10.1007/s101070050102zbMath0946.90067OpenAlexW4229642423MaRDI QIDQ1968794

Yanyan Li

Publication date: 22 June 2000

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://www.osti.gov/biblio/9490

zbMATH Keywords

traveling salesman problempolyhedral combinatorics2-matchingsubtour elimination problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items

Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Unnamed Item