MPI-INF Logo
Publications

Thesis (Server    domino.mpi-inf.mpg.de)

Thesis

Doctoral dissertation | @PhdThesis{FriedrichPhD2007, ... | Doktorarbeit

Friedrich, Tobias

Use and Avoidance of Randomness

Universität des Saarlandes, December, 2007

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.

Public
Download File(s):
Completed
13
December
2007
Raimund Seidel
Max-Planck-Institut für Informatik
Algorithms and Complexity Group
experts only
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