New inapproximability bounds for TSP
From MaRDI portal
Publication:494069
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)- Constant factor approximation for ATSP with two edge weights
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Private measures, random walks, and synthetic data
- Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
- Towards better inapproximability bounds for TSP: a challenge of global dependencies
- A deterministic better-than-3/2 approximation algorithm for metric TSP
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Scheduling on a graph with release times
- Weighted amplifiers and inapproximability results for travelling salesman problem
- The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
- Improved inapproximability for TSP
- On global integer extrema of real-valued box-constrained multivariate quadratic functions
- An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
- Hard to solve instances of the Euclidean traveling salesman problem
- On approximate data reduction for the Rural Postman Problem: Theory and experiments
- Traveling salesman problem across well-connected cities and with location-dependent edge lengths
- Improved inapproximability for TSP
- Reducing Path TSP to TSP
- On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time
- Approximation algorithms for the bus evacuation problem
- Approximation algorithms for some min-max postmen cover problems
- Approximating TSP walks in subcubic graphs
- Approximation algorithms for some extensions of the maximum profit routing problem
- New inapproximability bounds for TSP
- Perpetual maintenance of machines with different urgency requirements
- Constant factor approximation for ATSP with two edge weights (extended abstract)
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Twenty-two new approximate proof labeling schemes
- Vehicle routing with subtours
- Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
- Travelling on graphs with small highway dimension
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)
