On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
From MaRDI portal
Publication:1885277
DOI10.1007/s10107-004-0506-yzbMath1136.90031OpenAlexW2038458261MaRDI QIDQ1885277
Publication date: 28 October 2004
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-004-0506-y
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (18)
A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ A simple LP relaxation for the asymmetric traveling salesman problem ⋮ A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph ⋮ Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem ⋮ The salesman's improved tours for fundamental classes ⋮ Unnamed Item ⋮ A note on relatives to the Held and Karp 1-tree problem ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes ⋮ A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
This page was built for publication: On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
