License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.18
URN: urn:nbn:de:0030-drops-136634
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13663/
Go to the corresponding LIPIcs Volume Portal

Brodowsky, Ulrich A. ; Hougardy, Stefan

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

pdf-format:
LIPIcs-STACS-2021-18.pdf (0.8 MB)

Abstract

The 2-Opt heuristic is a simple improvement heuristic for the Traveling Salesman Problem. It starts with an arbitrary tour and then repeatedly replaces two edges of the tour by two other edges, as long as this yields a shorter tour. We will prove that for Euclidean Traveling Salesman Problems with n cities the approximation ratio of the 2-Opt heuristic is Θ(log n / log log n). This improves the upper bound of O(log n) given by Chandra, Karloff, and Tovey [Barun Chandra et al., 1999] in 1999.

BibTeX - Entry

@InProceedings{brodowsky_et_al:LIPIcs.STACS.2021.18,
  author =	{Brodowsky, Ulrich A. and Hougardy, Stefan},
  title =	{{The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13663},
  URN =		{urn:nbn:de:0030-drops-136634},
  doi =		{10.4230/LIPIcs.STACS.2021.18},
  annote =	{Keywords: traveling salesman problem, metric TSP, Euclidean TSP, 2-Opt, approximation algorithm}
}

Keywords: traveling salesman problem, metric TSP, Euclidean TSP, 2-Opt, approximation algorithm
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI