@article{Talvitie_Kangas_Niinimäki_Koivisto_2018, title={Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo}, volume={32}, url={https://ojs.aaai.org/index.php/AAAI/article/view/11528}, DOI={10.1609/aaai.v32i1.11528}, abstractNote={ <p> 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. </p> }, number={1}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Talvitie, Topi and Kangas, Kustaa and Niinimäki, Teppo and Koivisto, Mikko}, year={2018}, month={Apr.} }