Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies

DOI10.1007/978-3-319-22177-9_1zbMath1434.68676OpenAlexW1126480118MaRDI QIDQ2947865

Marek Karpinski

Publication date: 29 September 2015

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-22177-9_1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• An explicit lower bound for TSP with distances one and two
• TSP with bounded metrics
• On the approximability of the traveling salesman problem
• New Inapproximability Bounds for TSP
• TSP on Cubic and Subcubic Graphs
• Improved Inapproximability for TSP
• Approximation hardness of graphic TSP on cubic graphs
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• 8/7-approximation algorithm for (1,2)-TSP
• The Traveling Salesman Problem with Distances One and Two
• Some optimal inapproximability results
• Approximating Graphic TSP by Matchings

This page was built for publication: Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies