  We consider the following question. We are given a dense digraph $D$ with
minimum in- and out-degree at least $\alpha n$, where $\alpha>1/2$ is a
constant. The edges of $D$ are given edge costs $C(e),e\in E(D)$, where $C(e)$
is an independent copy of the uniform $[0,1]$ random variable $U$. Let
$C(i,j),i,j\in[n]$ be the associated $n\times n$ cost matrix where
$C(i,j)=\infty$ if $(i,j)\notin E(D)$. We show that w.h.p. the patching
algorithm of Karp finds a tour for the asymmetric traveling salesperson problem
that is asymptotically equal to that of the associated assignment problem.
Karp's algorithm runs in polynomial time.
