On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915855120465920 |
|---|---|
| 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). However, his proof requires $k \gg 1000$ and has a substantial gap. We provide the first rigorous proof for the PLS-completeness and at the same time drastically lower the value of $k$ to $k \geq 15$, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). Our result holds for both the general and the metric traveling salesman problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11270 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem Heimann, Sophia Hoang, Hung P. Hougardy, Stefan Data Structures and Algorithms 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). However, his proof requires $k \gg 1000$ and has a substantial gap. We provide the first rigorous proof for the PLS-completeness and at the same time drastically lower the value of $k$ to $k \geq 15$, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). Our result holds for both the general and the metric traveling salesman problem. |
| title | On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem |
| topic | Data Structures and Algorithms Combinatorics 68W25, 68W40, 68Q25, 90C27 F.2.2; G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2603.11270 |