22/06/2020

An improved approximation algorithm for ATSP

Vera Traub, Jens Vygen

Keywords: integrality ratio, approximation algorithms, traveling salesman problem

Abstract: We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and Végh [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+ε for any ε > 0. This also improves the upper bound on the integrality ratio from 319 to 22.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at STOC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers