Authors: Storch, Tobias
Title: Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
Language (ISO): en
Abstract: Surprisingly, general heuristics often solve hard combinatorial problems quite sufficiently, although they do not outperform specialized algorithms. Here, the behavior of simple randomized optimizers on the maximum clique problem is investigated. We focus on semi-random models for sparse graphs, in which an adversary is even allowed to insert a limited number of edges and not only to remove them. In the course of these investigations also the approximation behavior on general graphs and the optimization behavior on sparse graphs and further semi-random graph models are considered. With regard to the optimizers particular interest is given to the influences of the population size and the search operator.
Subject Headings: evolutionary algorithm
maximum clique problem
population size
randomized local search
run time analysis
semi-random graph
URI: http://hdl.handle.net/2003/26119
http://dx.doi.org/10.17877/DE290R-8712
Issue Date: 2006-06
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
21106.pdfDNB362.54 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.