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

preprint2020arXivOpen access

Abstract

The 2-Opt heuristic is one of the simplest algorithms for finding good solutions to the metric Traveling Salesman Problem. It is the key ingredient to the well-known Lin-Kernighan algorithm and often used in practice. So far, only upper and lower bounds on the approximation ratio of the 2-Opt heuristic for the metric TSP were known. We prove that for the metric TSP with nn cities, the approximation ratio of the 2-Opt heuristic is n/2\sqrt{n/2} and that this bound is tight.

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.