Helsinki Algorithms Seminar: "Counting Linear Extensions in Practice" Topi Talvitie
Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design
Map © OpenStreetMap. Some rights reserved.
Speaker:
Topi Talvitie
Title:
Counting Linear Extensions in Practice
Abstract:
The problem of counting the linear extensions of a partial order is a #P-complete problem that arises in numerous applications. Both exponential-time exact algorithms and polynomial-time approximation algorithms based on MCMC have been proposed.
We introduce two new approximation algorithms: a MCMC algorithm based on an embedding of the problem into a continuous space and a hybrid method combining exponential-time exact counting and sampling. We demonstrate experimentally that the MCMC algorithm exhibits polynomial-time characteristics, and that the combination of these algorithms significantly outperforms previous schemes.
This is joint work with Kustaa Kangas, Teppo Niinimäki and Mikko Koivisto.
**
Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.
Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.
For the season programme, please see the seminar webpage.