On the approximability of the traveling salesman problem
From MaRDI portal
Publication:2495698
In the paper the previously known inapproximability bounds for symmetric as well as asymmetric traveling salesman problems are improved by more than an order of magnitude. First, a new inapproximability bound for the asymmetric traveling salesman problem is given by providing a special reduction from maximum satisfiability of linear equations modulo 2 with three variables per equation. The reduction relies on a probabilistic construction of a graph with specialized properties, the so-called \(b\)-pusher, and is essentially nonconstructive. The same basic ideas (with a new set of gadgets) are then used to prove a new inapproximability bound for the symmetric traveling salesman problem.
Recommendations
- scientific article; zbMATH DE number 4095236
- On the approximability of the traveling salesman problem (extended abstract)
- Approximation algorithms for the traveling salesman problem
- The traveling salesman problem. Approximate algorithms
- On the solution of traveling salesman problems
- An approximation algorithm for the maximum traveling salesman problem
- An approximation algorithm for the maximum traveling salesman problem
- scientific article; zbMATH DE number 598850
- Approximate algorithms for the traveling salesman problem. II
- On Some Generalizations of the Travelling-Salesman Problem
Cited in
(59)- A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
- Operational estimators for the length of a traveling salesman tour
- Weighted amplifiers and inapproximability results for travelling salesman problem
- Approximation hardness of Travelling Salesman via weighted amplifiers
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- An LP-based approximation algorithm for the generalized traveling salesman path problem
- Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
- The traveling salesman problem: new polynomial approximation algorithms and domination analysis
- A domination algorithm for \(\{0,1\}\)-instances of the travelling salesman problem
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- New inapproximability bounds for TSP
- An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem
- Towards better inapproximability bounds for TSP: a challenge of global dependencies
- On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
- scientific article; zbMATH DE number 6613883 (Why is no real title available?)
- Approximation results for min-max path cover problems in vehicle routing
- Structural properties of hard metric TSP inputs (extended abstract)
- scientific article; zbMATH DE number 5859273 (Why is no real title available?)
- On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
- Improved inapproximability for TSP
- Improved inapproximability for TSP
- On the approximability of the traveling salesman problem (extended abstract)
- scientific article; zbMATH DE number 5158919 (Why is no real title available?)
- A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
- A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
- scientific article; zbMATH DE number 1305423 (Why is no real title available?)
- scientific article; zbMATH DE number 598850 (Why is no real title available?)
- On the Significance of the Initial Solution in Travelling Salesman Heuristics
- scientific article; zbMATH DE number 1054956 (Why is no real title available?)
- scientific article; zbMATH DE number 2080248 (Why is no real title available?)
- scientific article; zbMATH DE number 1486639 (Why is no real title available?)
- scientific article; zbMATH DE number 1499191 (Why is no real title available?)
- scientific article; zbMATH DE number 1534500 (Why is no real title available?)
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Spanning closed walks and TSP in 3-connected planar graphs
- On the Metric $s$--$t$ Path Traveling Salesman Problem
- Provably good solutions for the traveling salesman problem
- scientific article; zbMATH DE number 1839451 (Why is no real title available?)
- scientific article; zbMATH DE number 808804 (Why is no real title available?)
- New inapproximability bounds for TSP
- Quell
- TSP tours in cubic graphs: beyond 4/3
- Approximating the Metric TSP in Linear Time
- The analyst's traveling salesman theorem in graph inverse limits
- Spanning closed walks and TSP in 3-connected planar graphs
- A diagonal completion and 2-optimal procedure for the travelling salesman problem
- Travelling on graphs with small highway dimension
- A note on computational aspects of the Steiner traveling salesman problem
- Ailsa H. Land and her 1979 study of the traveling salesman problem: personal reminiscences and historical remarks
- Some contributions of Ailsa H. Land to the study of the traveling salesman problem
- Approximating the metric TSP in linear time
- An improved upper bound for the universal TSP on the grid
- A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
- 1.6-approximation algorithm for generalized traveling salesman path problem
- Vector TSP: a traveling salesperson problem with racetrack-like acceleration constraints
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- Efficiency of a local algorithm for solving the traveling salesman problem
- Approximation hardness of min-max tree covers
- Truncated \(M\)-travelling salesman problem
This page was built for publication: On the approximability of the traveling salesman problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2495698)
