2022/09/13 by Alan Frieze, Frieze, Alan, Peleg Michaeli +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.2209.06279
There is an error in an important lemma
arxiv created 2026/07/29 · arxiv updated 2026/07/30
We consider the following question. We are given a dense digraph D0 with minimum in- and out-degree at least αn, where α>0 is a constant. We then add random edges R to D0 to create a digraph D. Here an edge e is placed independently into R with probability n-ε where ε>0 is a small positive constant. The edges E(D) of D are given independent edge costs C=C(e),e∈ E(D), where C has a density f(x)=a+bx+o(x) as x→ 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∈[n] be the associated n× n cost matrix where C(i,j)=∞ if (i,j)∉ 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.