TSP with bounded metrics
From MaRDI portal
Publication:2495398
DOI10.1016/j.jcss.2005.12.001zbMath1125.90066OpenAlexW2048104107MaRDI QIDQ2495398
Marek Karpinski, Lars Engebretsen
Publication date: 30 June 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.12.001
Related Items (11)
Bipartite multigraphs with expander-like properties ⋮ Approximation hardness of graphic TSP on cubic graphs ⋮ Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles ⋮ Unconstrained traveling tournament problem is APX-complete ⋮ Scheduling on a graph with release times ⋮ On testing Hamiltonicity of graphs ⋮ Approximation bounds for Black Hole Search problems ⋮ New inapproximability bounds for TSP ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An explicit lower bound for TSP with distances one and two
- Bipartite multigraphs with expander-like properties
- Proof verification and the hardness of approximation problems
- On the approximability of the traveling salesman problem (extended abstract)
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- 8/7-approximation algorithm for (1,2)-TSP
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- The Traveling Salesman Problem with Distances One and Two
- Some optimal inapproximability results
This page was built for publication: TSP with bounded metrics
