New inapproximability bounds for TSP
DOI10.1016/J.JCSS.2015.06.003zbMATH Open1328.68076OpenAlexW2962875727WikidataQ55899759 ScholiaQ55899759MaRDI QIDQ494069FDOQ494069
Authors: 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
Recommendations
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Proof verification and the hardness of approximation problems
- Some optimal inapproximability results
- 8/7-approximation algorithm for (1,2)-TSP
- The Traveling Salesman Problem with Distances One and Two
- 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
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Title not available (Why is that?)
- A Randomized Rounding Approach to the Traveling Salesman Problem
- On the approximability of the traveling salesman problem
- Title not available (Why is that?)
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Approximating Graphic TSP by Matchings
- An explicit lower bound for TSP with distances one and two
- TSP with bounded metrics
- \(\frac {13}{9}\)-approximation for graphic TSP
- Title not available (Why is that?)
- Approximation hardness of graphic TSP on cubic graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (28)
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Approximating TSP walks in subcubic graphs
- Approximation algorithms for some extensions of the maximum profit routing problem
- Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
- Reducing Path TSP to TSP
- Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Vehicle routing with subtours
- Approximation algorithms for some min-max postmen cover problems
- On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time
- Approximation algorithms for the bus evacuation problem
- Traveling salesman problem across well-connected cities and with location-dependent edge lengths
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- On approximate data reduction for the Rural Postman Problem: Theory and experiments
- Hard to solve instances of the Euclidean traveling salesman problem
- Weighted amplifiers and inapproximability results for travelling salesman problem
- Perpetual maintenance of machines with different urgency requirements
- A deterministic better-than-3/2 approximation algorithm for metric TSP
- Travelling on graphs with small highway dimension
- Scheduling on a graph with release times
- An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
- Constant factor approximation for ATSP with two edge weights
- On global integer extrema of real-valued box-constrained multivariate quadratic functions
- Improved inapproximability for TSP
- Constant Factor Approximation for ATSP with Two Edge Weights
- The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
- Twenty-two new approximate proof labeling schemes
- Private measures, random walks, and synthetic data
This page was built for publication: New inapproximability bounds for TSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494069)
