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

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Matrix Rounding, Evolutionary Algorithms, and Hole Detection
Speaker:Christian Klein
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Promotionskolloquium
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:-- Not specified --
Date, Time and Location
Date:Monday, 23 June 2014
Duration:60 Minutes
Building:E1 4
In this thesis we study three different topics from the field of algorithms and data structures.

First, we investigate a problem from statistics.
We give two randomised algorithms that can round matrices of fractional values to integer-valued matrices.
These matrices will exhibit only small rounding errors for sums of initial row or column entries.
Both algorithms also round each entry up with probability equal to its fractional value.
We give a derandomisation of both algorithms.

Next, we consider the analysis of evolutionary algorithms (EAs).
First, we analyse an EA for the Single Source Shortest Path problem.
We give tight upper and lower bounds on the optimisation time of the EA. For this, we develop some new techniques for such analyses.
We also analyse an EA for the All-Pairs Shortest Path problem.
We show that adding crossover to this algorithm provably decreases its optimisation time.
This is the first time that the usefulness of crossover has been shown for a non-constructed combinatorial problem.

Finally, we examine how to retrieve the implicit geometric information hidden in the communications graph of a wireless sensor network.
We give an algorithm that is able to identify wireless nodes close to a hole in this network based on the connectivity information alone.
If the input fulfils several preconditions, then the algorithm finds a node near each boundary point and never misclassifies a node.

Name(s):Christian Klein
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Christian Klein2, 06/15/2014 10:47 PM -- Created document.