2026-08-18T03:36:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5626 2024-03-06T10:36:43Z ddc:004 open_access

Approximating the Regular Graphic TSP in Near Linear Time Chiplunkar, Ashish Vishwanathan, Sundar traveling salesperson problem approximation linear time We present a randomized approximation algorithm for computing traveling salesperson tours in undirected regular graphs. Given an n-vertex, k-regular graph, the algorithm computes a tour of length at most (1+frac 4+ln 4+varepsilon ln k-O(1)n, with high probability, in O(nk log k) time. This improves upon the result by Vishnoi ([Vishnoi12],FOCS 2012) for the same problem, in terms of both approximation factor, and running time. Furthermore, our result is incomparable with the recent result by Feige, Ravi, and Singh ([FeigeRS14], IPCO 2014), since our algorithm runs in linear time, for any fixed k. The key ingredient of our algorithm is a technique that uses edge-coloring algorithms to sample a cycle cover with O(n/log k) cycles, with high probability, in near linear time. Additionally, we also give a deterministic frac{3}{2}+O(frac{1}sqrt{k}) factor approximation algorithm for the TSP on n-vertex, k-regular graphs running in time O(nk). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ashish Chiplunkar and Sundar Vishwanathan 2015 Is Part Of LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2015.125 urn:nbn:de:0030-drops-56264 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.125 eng https://creativecommons.org/licenses/by/3.0/legalcode