EUVIMEDEUVIMED entdecken
Crossref

The Approximation Ratio of the k -Opt Heuristic for the Euclidean Traveling Salesman Problem

Ulrich A. Brodowsky, Stefan Hougardy, Xianghui Zhong

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →