Authors: Storch, Tobias
Title: how randomized search heuristics find maximum cliques in planar graphs
Language (ISO): en
Abstract: Surprisingly, general search heuristics often solve combinatorial problems quite sufficiently, although they do not outperform specialized algorithms. Here, the behavior of simple randomized optimizers on the maximum clique problem on planar graphs is investigated rigorously. The focus is on the worst-, average-, and semi-average-case behaviors. In semi-random planar graph models an adversary is allowed to modify moderately a random planar graph, where a graph is chosen uniformly at random among all planar graphs. With regard to the heuristics particular interest is given to the influences of the following four popular strategies to overcome local optima: local- vs. global-search, single- vs. multi-start, small vs. large population, and elitism vs. non-elitism selection. Finally, the black-box complexities of the planar graph models are analyzed.
Subject Headings: analysis of algorithms and problem complexity
Theory of computation
URI: http://hdl.handle.net/2003/26111
http://dx.doi.org/10.17877/DE290R-9024
Issue Date: 2006-03
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
20306.pdfDNB225.49 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.