Accession Number : ADA257791
Title : Location and Distribution of Local Optima
Descriptive Note : Final rept.
Corporate Author : GEORGIA INST OF TECH ATLANTA SCHOOL OF INDUSTRIAL AND SYSTEMS ENGINEERING
Personal Author(s) : Llewellyn, Donna C ; Whitaker, L M
Report Date : 30 Sep 1992
Pagination or Media Count : 112
Abstract : 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.
Descriptors : *MATHEMATICAL ANALYSIS , DISTRIBUTION , EDGES , GRAPHS , STRUCTURES , EXCHANGE , BERNOULLI DISTRIBUTION , PAPER , DEPTH , TIME , GUARANTEES , QUALITY
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE