New inapproximability bounds for TSP
From MaRDI portal
Publication:494069
DOI10.1016/j.jcss.2015.06.003zbMath1328.68076WikidataQ55899759 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
90C60: Abstract computational complexity for mathematical programming problems
90C27: Combinatorial optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, Travelling on graphs with small highway dimension, Reducing Path TSP to TSP, An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem, From symmetry to asymmetry: generalizing TSP approximations by parametrization, Perpetual maintenance of machines with different urgency requirements, A deterministic better-than-3/2 approximation algorithm for metric TSP, Approximation algorithms for the bus evacuation problem, On global integer extrema of real-valued box-constrained multivariate quadratic functions, Constant factor approximation for ATSP with two edge weights, Vehicle routing with subtours, Approximating TSP walks in subcubic graphs, Approximation algorithms for some extensions of the maximum profit routing problem, From symmetry to asymmetry: generalizing TSP approximations by parametrization, Weighted amplifiers and inapproximability results for travelling salesman problem, The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm, Approximation algorithms for some min-max postmen cover problems, Hard to solve instances of the Euclidean traveling salesman problem, Traveling salesman problem across well-connected cities and with location-dependent edge lengths, Constant Factor Approximation for ATSP with Two Edge Weights
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
