Journal
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20)
Volume -, Issue -, Pages 1-13Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3357713.3384233
Keywords
traveling salesman problem; approximation algorithms; integrality ratio
Ask authors/readers for more resources
We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and Vegh [STOC 2018]. 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available