Approximation hardness of graphic TSP on cubic graphs

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

zbMATH Keywords

traveling salesman problemapproximability

Mathematics Subject Classification ID

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