The Approximation Ratio of the k -Opt Heuristic for the Euclidean Traveling Salesman Problem
SIAM Journal on Computing · 31.08.2023 · 52 (4) · 841-864
DOI: 10.1137/21m146199x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 20.07.2023. Verfasst von Ulrich A. Brodowsky und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 19 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.
Abstract (Originalsprache)
The [Formula: see text]-Opt heuristic is a simple improvement heuristic for the traveling salesman problem. It starts with an arbitrary tour and then repeatedly replaces [Formula: see text] edges of the tour by [Formula: see text] other edges, as long as this yields a shorter tour. We will prove that for the 2-dimensional Euclidean traveling salesman problem with [Formula: see text] cities the approximation ratio of the [Formula: see text]-Opt heuristic is [Formula: see text]. This improves the upper bound of [Formula: see text] 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 [Formula: see text]. Our results not only hold for the Euclidean norm but extend to arbitrary [Formula: see text]-norms with [Formula: see text].
Förderung
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Brodowsky, U. A., Hougardy, S., & Zhong, X. (2023). The Approximation Ratio of the k -Opt Heuristic for the Euclidean Traveling Salesman Problem. SIAM Journal on Computing, 52(4), 841-864. https://doi.org/10.1137/21m146199x
Vancouver
Brodowsky UA, Hougardy S, Zhong X. The Approximation Ratio of the k -Opt Heuristic for the Euclidean Traveling Salesman Problem. SIAM Journal on Computing. 2023;52(4):841-864. doi:10.1137/21m146199x
BibTeX
@article{Brodowsky2023,
author = {Brodowsky, Ulrich A. and Hougardy, Stefan and Zhong, Xianghui},
title = {The Approximation Ratio of the k -Opt Heuristic for the Euclidean Traveling Salesman Problem},
journal = {SIAM Journal on Computing},
year = {2023},
volume = {52},
number = {4},
pages = {841--864},
doi = {10.1137/21m146199x}
}
EUVIMED