TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 23.01.2014


Page Content

to Navigation

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.

23.01.2014 16:15
Annabell Berger
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe