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 (1-3). pp. 213-219.

Abstract

The well-known 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.)


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr86-028
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 24 Oct 2011 14:23
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/28