Improved inapproximability for TSP

DOI10.1007/978-3-642-32512-0_21MaRDI QIDQ3167400zbMATH OpenOpenAlexFDO

Authors Michael Lampis

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.2497, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.709.3639

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Abstract: The Traveling Salesman Problem is one of the most studied problems in computational complexity and its approximability has been a long standing open question. Currently, the best known inapproximability threshold known is 220/219 due to Papadimitriou and Vempala. Here, using an essentially different construction and also relying on the work of Berman and Karpinski on bounded occurrence CSPs, we give an alternative and simpler inapproximability proof which improves the bound to 185/184.

Recommendations

• Improved inapproximability for TSP
• On the approximability of the traveling salesman problem
• New inapproximability bounds for TSP
• New inapproximability bounds for TSP
• On the approximability of the traveling salesman problem (extended abstract)

Cited in

(15)

• Approximating TSP walks in subcubic graphs
• Improving the robustness of EPS to solve the TSP
• Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• New inapproximability bounds for TSP
• Towards better inapproximability bounds for TSP: a challenge of global dependencies
• On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
• scientific article; zbMATH DE number 6347354 (Why is no real title available?)
• Improved inapproximability for TSP
• On the approximability of the traveling salesman problem (extended abstract)
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• Cubic TSP: A 1.3-Approximation
• New inapproximability bounds for TSP
• TSP tours in cubic graphs: beyond 4/3
• New semidefinite programming relaxations for the linear ordering and the traveling salesman problem

This page was built for publication: Improved inapproximability for TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167400)