2023/01/13 by Behnezhad, Soheil, Roghani, Mohammad, Rubinstein, Aviad +1 · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2301.05350
We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related \em 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 \widetildeO(n) time. This improves upon a (3/8-ε)-approximate \widetildeO(n √(n))-time algorithm of Chen, Kannan, and Khanna [ICALP'20]. Equipped with our path cover algorithm, we give an \widetildeO(n) time algorithm that estimates the cost of (1,2)-TSP within a factor of (1.5+ε) which is an improvement over a folklore (1.75 + ε)-approximate \widetildeO(n)-time algorithm, as well as a (1.625+ε)-approximate \widetildeO(n√(n))-time algorithm of [CHK ICALP'20]. For graphic TSP, we present an \widetildeO(n) algorithm that estimates the cost of graphic TSP within a factor of 1.83 which is an improvement over a 1.92-approximate \widetildeO(n) time algorithm due to [CHK ICALP'20, Behnezhad FOCS'21]. We show that the approximation can be further improved to 1.66 using n2-Ω(1) time. All of our \widetildeO(n) time algorithms are information-theoretically time-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.