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

DOI10.1007/S101070050102MaRDI QIDQ1968794zbMATH OpenOpenAlexFDO

Authors 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

2-matchingpolyhedral combinatoricssubtour elimination problemtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program
• scientific article; zbMATH DE number 1187146
• On the integrality gap of the subtour LP for the 1,2-TSP
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

Cited in

(6)

• A \(\frac{1}{2}\)-integral relaxation for the \(A\)-matching problem
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program
• Hidden Hamiltonian cycle recovery via linear programming
• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• A proof of the Boyd-Carr conjecture

This page was built for publication: A new bound for the ratio between the 2-matching problem and its linear programming relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1968794)