Sublinear Algorithms for TSP via Path Covers

01/13/2023
by   Soheil Behnezhad, et al.
0

We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related maximum path cover problem, which asks for a collection of vertex disjoint paths that include the maximum number of edges. We show that for any fixed ϵ > 0, there is an algorithm that (1/2 - ϵ)-approximates the maximum path cover size of an n-vertex graph in O(n) time. This improves upon a (3/8-ϵ)-approximate O(n √(n))-time algorithm of Chen, Kannan, and Khanna [ICALP'20]. Equipped with our path cover algorithm, we give O(n) time algorithms that estimate the cost of graphic TSP and (1, 2)-TSP up to factors of 1.83 and (1.5+ϵ), respectively. Our algorithm for graphic TSP improves over a 1.92-approximate O(n) time algorithm due to [CHK ICALP'20, Behnezhad FOCS'21]. Our algorithm for (1,2)-TSP improves over a folklore (1.75 + ϵ)-approximate O(n)-time algorithm, as well as a (1.625+ϵ)-approximate O(n√(n))-time algorithm of [CHK ICALP'20]. Our analysis of the running time uses connections to parallel algorithms and is information-theoretically optimal up to poly log n factors. Additionally, we show that our approximation guarantees for path cover and (1,2)-TSP hit a natural barrier: We show better approximations require better sublinear time algorithms for the well-studied maximum matching problem.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset