Analyzing the Held-Karp TSP bound: A monotonicity property with application

DOI10.1016/0020-0190(90)90028-VzbMath0698.68050OpenAlexW2063836932MaRDI QIDQ912624

David P. Williamson, David B. Shmoys

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90028-v

zbMATH Keywords

performance guaranteestraveling salesman problemlower boundsapproximation algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05)

Related Items

Approximation algorithms for inventory problems with submodular or routing costs, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, Matroid-based TSP rounding for half-integral solutions, The parsimonious property of cut covering problems and its applications, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, On approximately fair cost allocation in Euclidean TSP games, A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case, Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, 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, The traveling salesman problem on cubic and subcubic graphs, Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem, The salesman's improved tours for fundamental classes, Approximation algorithms for metric tree cover and generalized tour and tree covers, TSP on Cubic and Subcubic Graphs, Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems, A note on the prize collecting traveling salesman problem, Analysis of the Held-Karp lower bound for the asymmetric TSP, Survivable networks, linear programming relaxations and the parsimonious property, 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem, \(\frac{13}{9}\)-approximation for graphic TSP, Deterministic sampling algorithms for network design, An improved upper bound for the TSP in cubic 3-edge-connected graphs, Unnamed Item, Unnamed Item, On the core of traveling salesman games, The indefinite period traveling salesman problem, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, An improved approximation ratio for the minimum latency problem, Estimating the Held-Karp lower bound for the geometric TSP, Unnamed Item, LP-based algorithms for multistage minimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization
• Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
• Heuristic analysis, linear programming and branch and bound
• Maximum matching and a polyhedron with 0,1-vertices
• The Traveling-Salesman Problem and Minimum Spanning Trees