with Anastasios Sidiropoulos.

Submitted to the 30th Annual Symposium on Computational Geometry (2014).

Abstract:

We present a near-optimal polynomial-time approximation algorithm for the asymmetric traveling salesman problem for graphs of bounded orientable or non-orientable genus. Our algorithm achieves an approximation factor of O(f(g)) on graphs with genusg, wheref(n) is the best approximation factor achievable in polynomial time on arbitraryn-vertex graphs. In particular, the O(logn/log logn)-approximation algorithm for general graphs by Asadpouret al.[SODA 2010] immediately implies an O(logg/log logg)-approximation algorithm for genus-ggraphs. Moreover, using recent progress on the problem of approximating the genus of a graph, our O(logg/log logg)-approximation can be applied to bounded-degree graphs even if no genus-gembedding of the graph is given. Our result improves and generalizes the the O(√glogg)-approximation algorithm of Oveis Gharan and Saberi [SODA 2011], which applies only to graphs withorientablegenusgand requires a genus-gembedding as part of the input, even for bounded-degree graphs. Finally, our techniques yield a O(1)-approximation algorithm for ATSP on graphs of genusgwith running time 2^{O(g)}·n^{O(1)}.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 03 Dec 2013