Recommendations
Cites work
- scientific article; zbMATH DE number 3526435 (Why is no real title available?)
- scientific article; zbMATH DE number 1500530 (Why is no real title available?)
- scientific article; zbMATH DE number 6322171 (Why is no real title available?)
- 8/7-approximation algorithm for (1,2)-TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
- An explicit lower bound for TSP with distances one and two
- Approximating Graphic TSP by Matchings
- Approximation hardness of graphic TSP on cubic graphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Improved inapproximability for TSP
- On the approximability of the traveling salesman problem
- Proof verification and the hardness of approximation problems
- 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
- Some optimal inapproximability results
- TSP with bounded metrics
- The Traveling Salesman Problem with Distances One and Two
- \(\frac {13}{9}\)-approximation for graphic TSP
Cited in
(31)- Improved inapproximability for TSP
- 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
- Towards better inapproximability bounds for TSP: a challenge of global dependencies
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Reducing Path TSP to TSP
- Vehicle routing with subtours
- New inapproximability bounds for TSP
- Approximation algorithms for some min-max postmen cover problems
- Approximation algorithms for the bus evacuation problem
- The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
- On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time
- 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
- Constant factor approximation for ATSP with two edge weights (extended abstract)
- Weighted amplifiers and inapproximability results for travelling salesman problem
- Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
- Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
- 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
- Constant factor approximation for ATSP with two edge weights
- An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
- On global integer extrema of real-valued box-constrained multivariate quadratic functions
- Improved inapproximability for TSP
- 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)
