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\mathrm{/}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) $\mathrm{Pr}(C\ge x)\le \text{a}{e}^{-\text{b}x}$ for constants $\text{a},\text{b}>0$, or $f(x)=0$ for $x>\text{n}$ for some constant $\text{n}>0$. Let $C(i,j),i,j\in [n]$ be the associated $n\times n$ cost matrix where $C(i,j)=\mathrm{\infty }$ if $(i,j)\mathrm{\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.