Approximation hardness of graphic TSP on cubic graphs
From MaRDI portal
Publication:3194690
DOI10.1051/ro/2014062zbMath1341.68308arXiv1304.6800OpenAlexW2962909669MaRDI QIDQ3194690
Richard Schmied, Marek Karpinski
Publication date: 20 October 2015
Published in: RAIRO - Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.6800
Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (6)
Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ New Approximation Algorithms for (1,2)-TSP ⋮ New inapproximability bounds for TSP ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ Approximating TSP walks in subcubic graphs
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 improved upper bound for the TSP in cubic 3-edge-connected graphs
- TSP with bounded metrics
- New Inapproximability Bounds for TSP
- TSP Tours in Cubic Graphs: Beyond 4/3
- TSP on Cubic and Subcubic Graphs
- 8/7-approximation algorithm for (1,2)-TSP
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Traveling Salesman Problem with Distances One and Two
- Some optimal inapproximability results
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Approximating Graphic TSP by Matchings
This page was built for publication: Approximation hardness of graphic TSP on cubic graphs