New inapproximability bounds for TSP

DOI10.1016/j.jcss.2015.06.003zbMath1328.68076OpenAlexW2962875727WikidataQ55899759 ScholiaQ55899759MaRDI QIDQ494069

Marek Karpinski, Michael Lampis, Richard Schmied

Publication date: 31 August 2015

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.2015.06.003

zbMATH Keywords

travelling salesman problemhardness of approximation

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (24)

From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Constant Factor Approximation for ATSP with Two Edge Weights ⋮ Weighted amplifiers and inapproximability results for travelling salesman problem ⋮ Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ Perpetual maintenance of machines with different urgency requirements ⋮ A deterministic better-than-3/2 approximation algorithm for metric TSP ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ Scheduling on a graph with release times ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ Hard to solve instances of the Euclidean traveling salesman problem ⋮ Vehicle routing with subtours ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Traveling salesman problem across well-connected cities and with location-dependent edge lengths ⋮ Approximation algorithms for the bus evacuation problem ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ Constant factor approximation for ATSP with two edge weights ⋮ Travelling on graphs with small highway dimension ⋮ Reducing Path TSP to TSP ⋮ Approximating TSP walks in subcubic graphs ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem ⋮ Approximation algorithms for some extensions of the maximum profit routing problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Proof verification and the hardness of approximation problems
• Approximation hardness of graphic TSP on cubic graphs
• 8/7-approximation algorithm for (1,2)-TSP
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• The Traveling Salesman Problem with Distances One and Two
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Some optimal inapproximability results
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings

This page was built for publication: New inapproximability bounds for TSP