Storch, Tobias2009-05-122009-05-122006-06http://hdl.handle.net/2003/2611910.17877/DE290R-8712Surprisingly, 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.enReihe CI; 211-06evolutionary algorithmmaximum clique problempopulation sizerandomized local searchrun time analysissemi-random graph004report