Campus Event Calendar
Event Entry
What and Who
Use and Avoidance of Randomness
Tobias Friedrich
Max-Planck-Institut für Informatik - D1
Promotionskolloquium
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 13 December 2007
16:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Randomness is a crucial component in the design and analysis of many efficient algorithms. The 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.
Contact
Tobias Friedrich
--email hidden
passcode not visible
logged in users only
Tobias Friedrich, 11/30/2007 16:00
Tobias Friedrich, 11/30/2007 15:58 -- Created document.
Tobias Friedrich, 11/30/2007 15:58 -- Created document.