Exécution de notre outil de synthèse sur un nouvel article

Vérifiez l’article ci-dessous, puis lancez sa synthèse.


Approximating Regular Graphic TSP in near linear time

Ashish Chiplunkar, Sundar Vishwanathan

10 pages

Résumé : We present a randomized approximation algorithm for computing a traveling salesperson tour in undirected regular graphs. Given a $k$-regular graph with $n$ vertices, the algorithm computes a tour of length at most $\left(1+\frac{7}{\ln k-O(1)}\right)n$ in $O(nk \log k)$ time. This improves upon the recent result by Vishnoi (FOCS 2012) for the same problem, in terms of both approximation factor, and running time. 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.

Soumis à arXiv le 09 Avr. 2014