Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo

Topi Talvitie, Juho-Kustaa Kangas, Teppo Niinimäki, Mikko Koivisto

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

9 Citations (Scopus)


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.
Original languageEnglish
Title of host publication32nd AAAI Conference on Artificial Intelligence, AAAI 2018
PublisherAAAI Press
Number of pages8
ISBN (Electronic)9781577358008
Publication statusPublished - 2018
MoE publication typeA4 Conference publication
EventAAAI Conference on Artificial Intelligence - Hilton New Orleans Riverside, New Orleans, United States
Duration: 2 Feb 20187 Feb 2018
Conference number: 32

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
ISSN (Electronic)2374-3468


ConferenceAAAI Conference on Artificial Intelligence
Abbreviated titleAAAI
Country/TerritoryUnited States
CityNew Orleans


Dive into the research topics of 'Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo'. Together they form a unique fingerprint.

Cite this