Random combinatorial structures and randomized search heuristics [Elektronische Ressource] / vorgelegt von Daniel Johannsen
109 Pages
English

Random combinatorial structures and randomized search heuristics [Elektronische Ressource] / vorgelegt von Daniel Johannsen

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

Random Combinatorial Structuresand Randomized Search HeuristicsDissertationzur Erlangung des Grades desDoktors der Naturwissenschaftender Naturwissenschaftlich-Technischen Fakultätender Universität des Saarlandesvorgelegt vonDaniel JohannsenSaarbrücken7. April 20102Tag des Kolloquiums:15. Juli 2010Dekan der Naturwissenschaftlich-Technischen Fakultät I:Prof. Dr. Holger HermannsPrüfungsausschuss:Prof. Dr. Benjamin DoerrProf. Dr. Kurt MehlhornProf. Dr. Thomas Lengauer (Vorsitzender des Prüfungsausschusses)Dr. Tobias Friedrich (Akademischer Beisitzer)Berichterstatter:Prof. Dr. Benjamin DoerrProf. Dr. Kurt MehlhornProf. Xin Yao3AbstractThis thesis is concerned with the probabilistic analysis of random combinatorial struc-tures and the runtime analysis of randomized search heuristics.On the subject of random structures, we investigate two classes of combinatorialobjects. The first is the class of planar maps and the second is the class of generalizedparking functions. We identify typical properties of these structures and show strongconcentration results on the probabilities that these properties hold. To this end, wedevelop and apply techniques based on exact enumeration by generating functions. Forseveral types of random planar maps, this culminates in concentration results for thedegree sequence. For parking functions, we determine the distribution of the defect,the most characteristic parameter.

Subjects

Informations

Published by
Published 01 January 2010
Reads 5
Language English
Document size 1 MB