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 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.
graph algorithms analysis of algorithms explicit machine computation and programs (in optimization heading) explicit machine computation and programs (in computer science heading)