Aim

The application and investigation of probabilistic methods to algorithmic and structural problems in discrete mathematics.

Summary

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.

Research projects

The research program is arranged vertically into six projects, which are assigned to the individual research groups:

  1. Stable sets and special graph classes
  2. Combinatorial online-planning
  3. Evolution and phase transitions
  4. Randomness in the design and analysis of discrete algorithms
  5. Geometry and combinatorics of 0/1-Polytopes
  6. Enumeration and random generation

Guiding themes of the research program

As well as the above vertical division into seven projects, the research program may be arranged horizontally into four guiding themes. This arrangement emphasizes both the connections between the individual projects and their place within the overall program.

  1. Characterization of random objects
  2. Characterization of objects using randomness
  3. Analysis of algorithms with random input
  4. Analysis of randomized algorithms
last modified 10/05/05 (alkox-www)