The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913389386661888 |
|---|---|
| author | Heimann, Sophia Hoang, Hung P. Hougardy, Stefan |
| author_facet | Heimann, Sophia Hoang, Hung P. Hougardy, Stefan |
| contents | The $k$-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most $k$ edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the $k$-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the $k$-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires $k \gg 1000$ and has a substantial gap. We show the two properties above for a much smaller value of $k$, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for $k \geq 17$ and the exponential running time for $k \geq 5$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07061 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$ Heimann, Sophia Hoang, Hung P. Hougardy, Stefan Data Structures and Algorithms Discrete Mathematics Combinatorics 68W25, 68W40, 68Q25, 90C27 F.2.2; G.2.1; G.2.2 The $k$-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most $k$ edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the $k$-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the $k$-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires $k \gg 1000$ and has a substantial gap. We show the two properties above for a much smaller value of $k$, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for $k \geq 17$ and the exponential running time for $k \geq 5$. |
| title | The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$ |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 68W25, 68W40, 68Q25, 90C27 F.2.2; G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2402.07061 |