On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
From MaRDI portal
Publication:1885277
DOI10.1007/s10107-004-0506-yzbMath1136.90031MaRDI 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
90C35: Programming involving graphs or networks
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Related Items
Unnamed Item, A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering, On the Integrality Gap of the Prize-Collecting Steiner Forest LP, 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, A new integer programming formulation of the graphical traveling salesman problem, A new integer programming formulation of the graphical traveling salesman problem, On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy, A simple LP relaxation for the asymmetric traveling salesman problem, Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, 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, Shorter tours and longer detours: uniform covers and a bit beyond, The salesman's improved tours for fundamental classes, A note on relatives to the Held and Karp 1-tree problem, 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, A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
