SIAM Journal on Computing · 1999 · 114 citations · 10 references
ComputingComputer ScienceAlgorithmsMarkov Decision ProcessesOptimizationApproximation AlgorithmsCombinatorial OptimizationHeuristic OptimizationHeuristic SearchMetaheuristic OptimizationSearching AlgorithmsCombinatorial Optimization HeuristicsHeuristic AlgorithmsLocal SearchLocal Search AlgorithmsNeighborhood SearchTraveling Salesman ProblemTraveling Salesperson 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.
10
Covering a sphere with spheres
C. A. Rogers · Mathematika · 1963 · 151 citations
Local search and the local structure of NP-complete problems
Lov K. Grover · Operations Research Letters · 1992 · 123 citations