Randomized Rounding and Rumor Spreading with Stochastic Dependencies

The thesis is concerned with two uses of randomness, viz. randomized roundings and randomized rumor spreading algorithms.

The theorem of Beck and Fiala (1981) asserts that for every hypergraph and every set of vertex weights there is a rounding of the vertex weights such that the additive rounding error for all hyperedges is bounded by the maximum degree. This theorem will be extended to randomized roundings, that is, to roundings that are efficiently generated at random in such a way that each value is rounded up with probability equal to its fractional part.

The larger part of the thesis deals with randomized rumor spreading algorithms. These are protocols for disseminating information on graphs.
The classical randomized rumor spreading was introduced and first investigated by Frieze and Grimmett on the complete graph (1985).
We show a generalization of their results both in terms of the model used and in terms of the underlying graph.

We also investigate a quasirandom rumor spreading protocol introduced by Doerr, Friedrich, and Sauerwald (2008). We present a detailed analysis of its evolution and show that its performance and robustness match performance and robustness of the randomized rumor spreading protocol.