A probabilistic analysis of local search

H.M.M. Eikelder ten, M.G.A. Verhoeven, T.W.M. Vossen, E.H.L. Aarts

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review


We present a theoretical average-case analysis of a 2-opt algorithm for the traveling salesman problem. First, we give a model which allows us to compute the required number of steps and the distribution of final solutions found by a best improvement algorithm. This model is empirically validated for a restricted version of the 2-opt neighborhood. Secondly, we present a semi-empirical analysis of the average-case performance of an iterated 2-opt and Lin-Kernighan algorithm based on empirically obtained parameters.
Original languageEnglish
Title of host publicationMeta-heuristics : theory and applications
PublisherKluwer Academic Publishers
Number of pages14
ISBN (Print)0-7923-9700-2
Publication statusPublished - 1996
Externally publishedYes


Dive into the research topics of 'A probabilistic analysis of local search'. Together they form a unique fingerprint.

Cite this