Karp's patching algorithm on dense digraphs

2020/06/18 by Alan Frieze, Frieze, Alan
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.2006.10804

I found an error in the proof

arxiv created 2021/08/27 · arxiv updated 2021/08/31

Abstract

We consider the following question. We are given a dense digraph D with minimum in- and out-degree at least αn, where α>1/2 is a constant. The edges of D are given edge costs C(e),e∈ E(D), where C(e) is an independent copy of the uniform [0,1] random variable U. 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 that is asymptotically equal to that of the associated assignment problem. Karp's algorithm runs in polynomial time.

Related

• Karp's patching algorithm on dense digraph
• Karp's patching algorithm on random perturbations of dense digraphs
• Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
• Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
• The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus