Combinatorial optimization and the analysis of randomized search heuristics [Elektronische Ressource] / Frank Neumann

Combinatorial Optimizationand the Analysis ofRandomized Search HeuristicsDissertationzur Erlangung des akademischen GradesDoktor der Ingenieurwissenschaften(Dr. Ing.)der Technischen Fakult¨atder Christian-Albrechts-Universit¨atzu KielFrank NeumannKiel20061. Gutachter: Prof. Dr. Rudolf Berghammer2. Gutachter: Prof. Dr. Ingo Wegener3. Gutachter: Priv.-Doz. Dr. Benjamin DoerrTag der mu¨ndlichen Pru¨fung: 19. Juli 20063AbstractRandomized search heuristics have widely been applied to complex engineering problemsas well as to problems from combinatorial optimization. We investigate the runtime be-havior of randomized search heuristics and present runtime bounds for these heuristicson some well-known combinatorial optimization problems. Such analyses can help to un-derstand better the working principle of these algorithms on combinatorial optimizationproblems as well as help to design better algorithms for a newly given problem. Our anal-yses mainly consider evolutionary algorithms that have achieved good results on a wideclass of NP-hard combinatorial optimization problems. We start by analyzing some easysingle-objective optimization problems such as the minimum spanning tree problem or theproblem of computing an Eulerian cycle of a given Eulerian graph and prove bounds onthe runtime of simple evolutionary algorithms.