Operations Research · 1978 · 82 citations · 7 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationHeuristic OptimizationHeuristic SearchMetaheuristic OptimizationGlobal OptimaLocal OptimaLocal SearchLocal Search AlgorithmsTraveling Salesman ProblemTraveling Salesperson Problem
We construct instances of the symmetric traveling salesman problem with n = 8k cities that have the following property: There is exactly one optimal tour with cost n, and there are 2 k−1 (k − 1)! tours that are next-best, have arbitrarily large cost, and cannot be improved by changing fewer than 3k edges. Thus, there are many local optima with arbitrarily high cost. It appears that local search algorithms are ineffective when applied to these problems. Even more catastrophic examples are available in the non-symmetric case.
7
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text
Computer Solutions of the Traveling Salesman Problem
Shen Lin · Bell System Technical Journal · 1965 · 2K citations
P-Complete Approximation Problems
Sartaj Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976 · 1.7K citations · Full text