Karp's patching algorithm on random perturbations of dense digraphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915298256355328 |
|---|---|
| author | Frieze, Alan Michaeli, Peleg |
| author_facet | Frieze, Alan Michaeli, Peleg |
| contents | We consider the following question. We are given a dense digraph $D_0$ with minimum in- and out-degree at least $αn$, where $α>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^{-ε}$ where $ε>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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_06279 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Karp's patching algorithm on random perturbations of dense digraphs Frieze, Alan Michaeli, Peleg Combinatorics We consider the following question. We are given a dense digraph $D_0$ with minimum in- and out-degree at least $αn$, where $α>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^{-ε}$ where $ε>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. |
| title | Karp's patching algorithm on random perturbations of dense digraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2209.06279 |