Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
Loading...
Date
2006-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Table of contents
Keywords
evolutionary algorithm, maximum clique problem, population size, randomized local search, run time analysis, semi-random graph