Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF D1 Publications :: Thesis :: Friedrich, Tobias


MPI-INF D1 Publications
Show all entries of:this year (2019)last year (2018)two years ago (2017)Open in Notes
Action:login to update

Thesis - Doctoral dissertation | @PhdThesis | Doktorarbeit


Author
Author(s)*:Friedrich, Tobias
BibTeX citekey*:FriedrichPhD2007
Language:English

Title, School
Title*:Use and Avoidance of Randomness
School:Universität des Saarlandes
Type of Thesis*:Doctoral dissertation
Month:December
Year:2007


Note, Abstract, Copyright
LaTeX Abstract:Randomness is a crucial component in the design and analysis of many efficient algorithms.

This thesis covers three aspects of randomness in computer science.
In the first chapter we examine a deterministic analogue
to the random walk and prove that it resembles the random walk closely
on a two-dimensional grid, but not on regular trees. We also propose and analyse
a quasirandom analogue to the broadcasting model for disseminating information in networks
and show that it achieves similar or better broadcasting times with a greatly reduced use of random bits.

In the second chapter we present the first average-case analysis of three different
algorithms for maintaining a topological ordering of
the nodes of a directed acyclic graph under dynamic updates.
We prove an expected runtime
which is significantly less than the best known
worst-case bound for this problem.

We finish with a third chapter that deals with randomized search heuristics.
We examine the impact of different diversity mechanisms on the runtime of a
single-objective evolutionary algorithm. We also show how this can
exponentially slow down evolutionary algorithms for
multi-objective problems.

Download Access Level:Public
Download File(s):

Referees, Status, Dates
Status:Completed
Date Kolloquium:13 December 2007
Chair Kolloquium:Raimund Seidel

Correlation
MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
Audience:experts only
Appearance:MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:
@PHDTHESIS{FriedrichPhD2007,
AUTHOR = {Friedrich, Tobias},
TITLE = {Use and Avoidance of Randomness},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2007},
TYPE = {Doctoral dissertation}
MONTH = {December},
}





Entry last modified by Tobias Friedrich, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Tobias Friedrich
Created
01/15/2008 05:29:20 PM
Revision
0.



Editor
Tobias Friedrich



Edit Date
01/15/2008 05:29:20 PM