Karp's patching algorithm on random perturbations of dense digraphs

arXiv2209.06279MaRDI QIDQ6508032FDOQ6508032

Authors: Alan Frieze, Peleg Michaeli 

Abstract: We consider the following question. We are given a dense digraph $D_0$ with minimum in- and out-degree at least $alphan$, where $alpha>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^{-epsilon}$ where $epsilon>0$ is a small positive constant. The edges of $D$ are given edge costs $C(e),einE(D)$, where $C(e)$ is an independent copy of the exponential mean one random variable $EXP(1)$ i.e. $Pr(EXP(1)geqx)=e^{-x}$. Let $C(i,j),i,jin[n]$ be the associated $nimesn$ cost matrix where $C(i,j)=infty$ if $(i,j)otinE(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.

This page was built for publication: Karp's patching algorithm on random perturbations of dense digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508032)