Location and Distribution of Local Optima
Donna Crystal Llewellyn, L. M. Whitaker · 1992
In this paper, we present a probabilistic analysis of the time versus solution quality tradeoff of different implementations of a basic sequential edge exchange procedure for a Traveling Salesman Problem. Our TSP will be on a complete graph with edge weights assigned independently and identically according to a Bernoulli distribution. One implementation of the procedure is a generalization of the Lin-Kernighan heuristic. For this implementation, we find asymptotic performance guarantees which decrease geometrically as the depth of the search increases. The basic search procedure may be implemented using a 2- change neighborhood structure. This enables us to find an asymptotic performance guarantee for a 2-opt procedure.