On the approximability of the traveling salesman problem
From MaRDI portal
Publication:2495698
DOI10.1007/s00493-006-0008-zzbMath1106.90071OpenAlexW2059222268MaRDI QIDQ2495698
Christos H. Papadimitriou, Santosh Vempala
Publication date: 2 January 2007
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-006-0008-z
Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (19)
On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Approximating the Metric TSP in Linear Time ⋮ Weighted amplifiers and inapproximability results for travelling salesman problem ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Approximating the metric TSP in linear time ⋮ Spanning closed walks and TSP in 3-connected planar graphs ⋮ New inapproximability bounds for TSP ⋮ Quell ⋮ Approximation hardness of min-max tree covers ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ Approximation results for min-max path cover problems in vehicle routing ⋮ New semidefinite programming relaxations for the linear ordering and the traveling salesman problem ⋮ Structural Properties of Hard Metric TSP Inputs ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Travelling on graphs with small highway dimension ⋮ Unnamed Item
This page was built for publication: On the approximability of the traveling salesman problem
