A new bound for the ratio between the 2-matching problem and its linear programming relaxation
From MaRDI portal
Publication:1968794
DOI10.1007/s101070050102zbMath0946.90067OpenAlexW4229642423MaRDI QIDQ1968794
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
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