2013/04/05 by Jeff Erickson, Erickson, Jeff, Anastasios Sidiropoulos +1
Decision Sciences · #Auction Theory and Applications
paper · pdf · doi:10.48550/arxiv.1304.1810
We present a near-optimal polynomial-time approximation algorithm for the\nasymmetric traveling salesman problem for graphs of bounded orientable or\nnon-orientable genus. Our algorithm achieves an approximation factor of O(f(g))\non graphs with genus g, where f(n) is the best approximation factor achievable\nin polynomial time on arbitrary n-vertex graphs. In particular, the\nO(log(n)/loglog(n))-approximation algorithm for general graphs by Asadpour et\nal. [SODA 2010] immediately implies an O(log(g)/loglog(g))-approximation\nalgorithm for genus-g graphs. Our result improves the\nO(sqrt(g)*log(g))-approximation algorithm of Oveis Gharan and Saberi [SODA\n2011], which applies only to graphs with orientable genus g; ours is the first\napproximation algorithm for graphs with bounded non-orientable genus.\n Moreover, using recent progress on approximating the genus of a graph, our\nO(log(g) / loglog(g))-approximation can be implemented even without an\nembedding when the input graph has bounded degree. In contrast, the\nO(sqrt(g)*log(g))-approximation algorithm of Oveis Gharan and Saberi requires a\ngenus-g embedding as part of the input.\n Finally, our techniques lead to a O(1)-approximation algorithm for ATSP on\ngraphs of genus g, with running time 2O(g)*nO(1).\n