An improved approximation algorithm for ATSP
| Autor: | Jens Vygen, Vera Traub |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
021103 operations research Discrete Mathematics (cs.DM) 0211 other engineering and technologies Approximation algorithm 0102 computer and information sciences 02 engineering and technology 01 natural sciences Travelling salesman problem Upper and lower bounds Reduction (complexity) Combinatorics 010201 computation theory & mathematics Computer Science - Data Structures and Algorithms FOS: Mathematics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) Mathematics Computer Science - Discrete Mathematics |
| Zdroj: | STOC |
| DOI: | 10.48550/arxiv.1912.00670 |
| Popis: | We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and V\'egh. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from $506$ to $22+\epsilon$ for any $\epsilon > 0$. This also improves the upper bound on the integrality ratio from $319$ to $22$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|