New inapproximability bounds for TSP
Copyright policy )New inapproximability bounds for TSP
In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.
- University of Bonn Germany
- Hausdorff Center for Mathematics Germany
- Royal Institute of Technology Sweden
- Kyoto University Japan
- Research Institute for Mathematical Sciences Japan
FOS: Computer and information sciences, Combinatorial optimization, Discrete Mathematics (cs.DM), hardness of approximation, Computational Complexity (cs.CC), travelling salesman problem, Computer Science - Computational Complexity, Optimization and Control (math.OC), Computer Science - Data Structures and Algorithms, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Abstract computational complexity for mathematical programming problems, Mathematics - Optimization and Control, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Combinatorial optimization, Discrete Mathematics (cs.DM), hardness of approximation, Computational Complexity (cs.CC), travelling salesman problem, Computer Science - Computational Complexity, Optimization and Control (math.OC), Computer Science - Data Structures and Algorithms, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Abstract computational complexity for mathematical programming problems, Mathematics - Optimization and Control, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).72 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!