| Autor: |
BRODOWSKY, ULRICH A., HOUGARDY, STEFAN, XIANGHUI ZHONG |
| Předmět: |
|
| Zdroj: |
SIAM Journal on Computing; 2023, Vol. 52 Issue 4, p841-864, 24p |
| Abstrakt: |
The k-Opt heuristic is a simple improvement heuristic for the traveling salesman problem. It starts with an arbitrary tour and then repeatedly replaces k edges of the tour by k other edges, as long as this yields a shorter tour. We will prove that for the 2-dimensional Euclidean traveling salesman problem with n cities the approximation ratio of the k-Opt heuristic is Θ (log n/ log log n). This improves the upper bound of O(log n) given by Chandra, Karloff, and Tovey in [SIAM J. Comput., 28 (1999), pp. 1998--2029] and provides for the first time a nontrivial lower bound for the case k >3. Our results not only hold for the Euclidean norm but extend to arbitrary p-norms with 1 < p < ∞ . [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
