New results on the old k-opt algorithm for the traveling salesman problem

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...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1999, Vol.28 (6), p.1998-2029
Main Authors: CHANDRA, B, KARLOFF, H, TOVEY, C
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Calculus of variations and optimal control
Combinatorics
Combinatorics. Ordered structures
Computer science
Computer science
control theory
systems
Exact sciences and technology
Graph theory
Graphs
Heuristic
Mathematical analysis
Mathematics
Sciences and techniques of general use
Theoretical computing
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0097-5397
1095-7111
DOI:10.1137/s0097539793251244