Max-Planck-Institut für Informatik
max planck institut
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 (2020)last year (2019)two years ago (2018)Open in Notes
Action:login to update

Thesis - Doctoral dissertation | @PhdThesis | Doktorarbeit

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

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

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
Date Kolloquium:13 December 2007
Chair Kolloquium:Raimund Seidel

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:
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)

Tobias Friedrich
01/15/2008 05:29:20 PM

Tobias Friedrich

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