Towards better inapproximability bounds for TSP: a challenge of global dependencies
DOI10.1007/978-3-319-22177-9_1zbMATH Open1434.68676OpenAlexW1126480118MaRDI QIDQ2947865FDOQ2947865
Authors: 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
Recommendations
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
- Some optimal inapproximability results
- New inapproximability bounds for TSP
- 8/7-approximation algorithm for (1,2)-TSP
- The Traveling Salesman Problem with Distances One and Two
- 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 \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
- On the approximability of the traveling salesman problem
- Approximating Graphic TSP by Matchings
- Improved inapproximability for TSP
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- An explicit lower bound for TSP with distances one and two
- TSP with bounded metrics
- TSP on cubic and subcubic graphs
- Approximation hardness of graphic TSP on cubic graphs
- Title not available (Why is that?)
This page was built for publication: Towards better inapproximability bounds for TSP: a challenge of global dependencies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947865)
