  Let the costs $C(i,j)$ for an instance of the Asymmetric Traveling
Salesperson Problem (ATSP) be independent copies of an random variable $C$ that
(i) satisfies $\Pr(C\geq x)=1-x+O(x^2)$ as $x\to 0$ and (ii) has an exponential
tail. We describe an algorithm that solves ATSP exactly in time
$e^{\log^{2+o(1)}n}$, w.h.p.
