Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo
Abstract
Counting the linear extensions of a given partial order is a #P-complete problem that arises in numerous applications. For polynomial-time approximation, several Markov chain Monte Carlo schemes have been proposed; however, little is known of their efficiency in practice. This work presents an empirical evaluation of the state-of-the-art schemes and investigates a number of ideas to enhance their performance. In addition, we introduce a novel approximation scheme, adaptive relaxation Monte Carlo (ARMC), that leverages exact exponential-time counting algorithms. We show that approximate counting is feasible up to a few hundred elements on various classes of partial orders, and within this range ARMC typically outperforms the other schemes.
Cite
Text
Talvitie et al. "Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11528Markdown
[Talvitie et al. "Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/talvitie2018aaai-counting/) doi:10.1609/AAAI.V32I1.11528BibTeX
@inproceedings{talvitie2018aaai-counting,
title = {{Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo}},
author = {Talvitie, Topi and Kangas, Kustaa and Niinimäki, Teppo Mikael and Koivisto, Mikko},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {1431-1438},
doi = {10.1609/AAAI.V32I1.11528},
url = {https://mlanthology.org/aaai/2018/talvitie2018aaai-counting/}
}