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

Tolson Bell, Alan Frieze

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 distributi…