Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs

Daniel Marx, Ario Salmasi, Anastasios Sidiropoulos

In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find a closed walk of minimum cost in a directed graph visiting every vertex. We consider the approximability…