Matrix Rounding, Evolutionary Algorithms, and Hole Detection

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.