Improved Lower Bounds on the Approximability of the Traveling Salesman Problem

DOI10.1051/ita:2000115zbMath0971.68075OpenAlexW2160111458MaRDI QIDQ4522114

Sebastian Seibert, Hans-Joachim Böckenhauer

Publication date: 30 October 2001

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2000__34_3_213_0/

zbMATH Keywords

traveling salesman problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality ⋮ On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ A Modern View on Stability of Approximation ⋮ New inapproximability bounds for TSP ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ TSP with bounded metrics ⋮ On the Hardness of Reoptimization ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance guarantees for the TSP with a parameterized triangle inequality
• Approximation algorithms for the TSP with sharpened triangle inequality
• Lectures on proof verification and approximation algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On the approximability of the traveling salesman problem (extended abstract)
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• The Traveling Salesman Problem with Distances One and Two
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities