Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p

Abstract

Let the costs $C(i,j)$ for an instance of the Asymmetric Traveling Salesperson Problem (ATSP) be independent copies of a non-negative random variable $C$ from a class of distributions that include the uniform $[0,1]$ distribution and the exponential mean 1 distribution with mean 1. We describe an algorithm that solves ATSP exactly in time $e^{{\log }^{2+o(1)}n}$, w.h.p.

arXiv comment20 pages