A Probabilistic Analysis of the Switching Algorithm for the Euclidean TSP
Kern, Walter
(1989)
A Probabilistic Analysis of the Switching Algorithm for the Euclidean TSP.
Published in:
Mathematical programming : Series A Vol. 44 (13).
pp. 213219.
Abstract
The wellknown switching algorithm proposed by Lin and Kernighan for the Euclidean Travelling Salesman Problem has proved to be a simple efficient algorithm for medium size problems (though it often gets trapped in local optima). Although its complexity status is still open, it has been observed to be polynomially bounded in practice, when applied to uniformly distributed points in the unit square. In this paper this polynomial behaviour is derived theoretically. (However, we will come up with a bound of O(n 18) with probability 1 –c/n, whereas in practice the algorithm works slightly better.)
Item Type:  Article 

Citations:  15 (Google Scholar)  9 (Web of Science) 
Uncontrolled Keywords:  Euclidean Traveling Salesman kswitching algorithm probabilistic analysis simulated annealing 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr86028 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  24 Oct 2011 14:23 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/28 