New Results on the Old <i>k</i>-opt Algorithm for the Traveling Salesman Problem

Barun Chandra, Howard Karloff, Craig A. Tovey

SIAM Journal on Computing · 1999 · 114 citations · 10 references

Concepts

Abstract

Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were previously known. This paper develops several results, some worst-case and some probabilistic, on the performance of 2- and k-opt local search for the traveling salesman problem, with respect to both the quality of the solution and the speed with which it is obtained.

References

10