A Near-Optimal Approximation Algorithm for Asymmetric TSP on Embedded Graphs

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 genus g, where f(n) is the best approximation factor achievable in polynomial time on arbitrary n-vertex graphs. In particular, the O(log n/log log n)-approximation algorithm for general graphs by Asadpour et al. [SODA 2010] immediately implies an O(log g/log log g)-approximation algorithm for genus-g graphs. Moreover, using recent progress on the problem of approximating the genus of a graph, our O(log g/log log g)-approximation can be applied to bounded-degree graphs even if no genus-g embedding of the graph is given. Our result improves and generalizes the the O(√g log g)-approximation algorithm of Oveis Gharan and Saberi [SODA 2011], which applies only to graphs with orientable genus g and requires a genus-g embedding as part of the input, even for bounded-degree graphs. Finally, our techniques yield a O(1)-approximation algorithm for ATSP on graphs of genus g with running time 2^O(g)·n^O(1).

A near-optimal approximation algorithm for asymmetric TSP on embedded graphs