Sie sind hier

## Efficient (Uniform) Sampling of Combinatorial Structures

Dr. Annabell Berger (Martin-Luther-Universität Halle-Wittenberg)

The sampling of random combinatorial structures is a useful tool in various fields like network analysis, combinatorial optimization or statistical physics. The main task can be formulated as follows: Given a set of combinatorial objects, we want to choose an element of this set randomly with respect to a given probability distribution, mostly the uniform distribution. The method of choice is often the use of Markov Chain Monte Carlo Simulation. We explain symptomatic difficulties to prove the efficiency of such methods in a practical sense, formulate current challenges and show on the example of perfect matchings our first approaches to overcome these problems.

Date
Speaker
Location
Language
23.01.2014 16:15
Annabell Berger
TEL 512
english