Karp's patching algorithm on random perturbations of dense digraphs

Abstract

We consider the following question. We are given a dense digraph $D_0$ with minimum in- and out-degree at least $\hat{I}\pm n$, where $\hat{I}\pm >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^{-\hat{I}\mu }$ where $\hat{I}\mu >0$ is a small positive constant. The edges $E(D)$ of $D$ are given independent edge costs $C=C(e),e\in E(D)$, where $C$ has a density $f(x)=a+bx+o(x)$ as $x\to 0$. Here $a>0,b$ are constants. The prime examples will be the uniform $[0,1]$ distribution ($a=1,b=0$) and the exponential mean 1 distribution $EXP(1)$ ($a=1,b=-1$). 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 whose cost is asymptotically equal to the cost of the associated assignment problem. Karp's algorithm runs in polynomial time.

There is an error in an important lemma