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


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a257791.pdf


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