FG 413: Algorithms, Structure, Randomness II

The design and analysis of algorithms is related to insights into the structure of the objects which act as input for the algorithms under consideration. The central theme of this research program is to examine the role that randomness plays in this relationship. In particular, we investigate the effects of adding randomness on algorithmic and structural problems in discrete mathematics.

Randomness is both the object and method of research. In order to obtain structural knowledge, we seek properties which random objects possess with high probability, at the same time we use randomness to characterize objects. This duality is also encountered in the study of algorithmic problems. We investigate the behaviour of algorithms on random inputs, while on the other hand, we analyse processes whose decisions involve a random component.

On the algorithmic side, the focus of attention is on combinatorial optimization problems. In such problems, polytopes, graphs and partial orders occur as natural objects for structural investigation. This research program combines the individual expertise and capabilities which the participating research groups have acquired through the use of various approaches within the fields algorithms, structure and randomness.