Karp's patching algorithm on dense digraph

We consider the following question.

We are given a dense digraph $D$ with $n$ vertices and minimum in- and out-degree at least $\alpha n$, where $\alpha>1/2$ is a constant.

The edges $E(D)$ of $D$ are given independent edge costs $C(e),e\in E(D)$, such that (i) $C$ has a density $f$ that satisfies $f(x)=a+bx+O(x^2)$, for constants $a>0,b$ as $x\to 0$ and such that in general either (ii) $\Pr(C\geq x)\leq \a e^{-\b x}$ for constants $\a,\b>0$, or $f(x)=0$ for $x>\n$ for some constant $\n>0$.

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$.

We show that w.h.p.

(a small modification to) 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.

The algorithm runs in polynomial time.