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

preprint2021arXivOpen access

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 nn cities the approximation ratio of the 2-Opt heuristic is Θ(log⁡n/log⁡log⁡n)Θ(\log n/ \log \log n). This improves the upper bound of O(log⁡nO(\log n) given by Chandra, Karloff, and Tovey [3] in 1999.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.