On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2019
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914916825300992 |
|---|---|
| author | Zhong, Xianghui |
| author_facet | Zhong, Xianghui |
| contents | The $k$-Opt and Lin-Kernighan algorithm are two of the most important local search approaches for the Metric TSP. Both start with an arbitrary tour and make local improvements in each step to get a shorter tour. We show that for any fixed $k\geq 3$ the approximation ratio of the $k$-Opt algorithm for Metric TSP is $O(\sqrt[k]{n})$. Assuming the Erdős girth conjecture, we prove a matching lower bound of $Ω(\sqrt[k]{n})$. Unconditionally, we obtain matching bounds for $k=3,4,6$ and a lower bound of $Ω(n^{\frac{2}{3k-3}})$. Our most general bounds depend on the values of a function from extremal graph theory and are tight up to a factor logarithmic in the number of vertices unconditionally. Moreover, all the upper bounds also apply to a parameterized generalization of the Lin-Kernighan algorithm with appropriate parameters. We also show that the approximation ratio of $k$-Opt for Graph TSP is $Ω\left(\frac{\log(n)}{\log\log(n)}\right)$ and $O\left(\left(\frac{\log(n)}{\log\log(n)}\right)^{\log_2(9)+ε}\right)$ for all $ε>0$. For the (1,2)-TSP we give a lower bound of $\frac{11}{10}$ on the approximation ratio of the $k$-improv and $k$-Opt algorithm for arbitrary fixed $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1909_12755 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm Zhong, Xianghui Discrete Mathematics Data Structures and Algorithms Combinatorics 68W40, 68W25 F.2.2; G.2.1 The $k$-Opt and Lin-Kernighan algorithm are two of the most important local search approaches for the Metric TSP. Both start with an arbitrary tour and make local improvements in each step to get a shorter tour. We show that for any fixed $k\geq 3$ the approximation ratio of the $k$-Opt algorithm for Metric TSP is $O(\sqrt[k]{n})$. Assuming the Erdős girth conjecture, we prove a matching lower bound of $Ω(\sqrt[k]{n})$. Unconditionally, we obtain matching bounds for $k=3,4,6$ and a lower bound of $Ω(n^{\frac{2}{3k-3}})$. Our most general bounds depend on the values of a function from extremal graph theory and are tight up to a factor logarithmic in the number of vertices unconditionally. Moreover, all the upper bounds also apply to a parameterized generalization of the Lin-Kernighan algorithm with appropriate parameters. We also show that the approximation ratio of $k$-Opt for Graph TSP is $Ω\left(\frac{\log(n)}{\log\log(n)}\right)$ and $O\left(\left(\frac{\log(n)}{\log\log(n)}\right)^{\log_2(9)+ε}\right)$ for all $ε>0$. For the (1,2)-TSP we give a lower bound of $\frac{11}{10}$ on the approximation ratio of the $k$-improv and $k$-Opt algorithm for arbitrary fixed $k$. |
| title | On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics 68W40, 68W25 F.2.2; G.2.1 |
| url | https://arxiv.org/abs/1909.12755 |