2026-07-25T23:12:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13663 2024-03-06T10:52:36Z ddc:004 open_access

The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem Brodowsky, Ulrich A. Hougardy, Stefan traveling salesman problem metric TSP Euclidean TSP 2-Opt approximation algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ulrich A. Brodowsky and Stefan Hougardy 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.18 urn:nbn:de:0030-drops-136634 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.18 eng https://creativecommons.org/licenses/by/4.0/legalcode