  We consider the following question. We are given a dense digraph $D_0$ with
minimum in- and out-degree at least $\alpha n$, where $\alpha>0$ is a constant.
We then add random edges $R$ to $D_0$ to create a digraph $D$. Here an edge $e$
is placed independently into $R$ with probability $n^{-\epsilon}$ where
$\epsilon>0$ is a small positive constant. The edges of $D$ are given edge
costs $C(e),e\in E(D)$, where $C(e)$ is an independent copy of the exponential
mean one random variable $EXP(1)$ i.e. $\Pr(EXP(1)\geq x)=e^{-x}$. 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.
