The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus
arXiv:0909.2849
Abstract
We give a constant factor approximation algorithm for the asymmetric traveling salesman problem when the support graph of the solution of the Held-Karp linear programming relaxation has bounded orientable genus.