2025/05/27 by Alan Frieze, Frieze, Alan
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2505.21645
There is an error in an important lemma
openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · arxiv created 2026/07/29 · arxiv updated 2026/07/30 · openalex updated_date 2026/08/02
We consider the following question. We are given a dense digraph D with n vertices and minimum in- and out-degree at least αn, where α>1/2 is a constant. The edges E(D) of D are given independent edge costs C(e),e∈ E(D), such that (i) C has a density f that satisfies f(x)=a+bx+O(x2), for constants a>0,b as x→ 0 and such that in general either (ii) Pr(C≥ x)≤ \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∈[n] be the associated n× n cost matrix where C(i,j)=∞ if (i,j)∉ 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.