Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo

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

Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo

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

University of Helsinki

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

13 Citations (Scopus)

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.

Original language	English
Title of host publication	32nd AAAI Conference on Artificial Intelligence, AAAI 2018
Publisher	AAAI Press
Pages	1431-1438
Number of pages	8
ISBN (Electronic)	9781577358008
Publication status	Published - 2018
MoE publication type	A4 Conference publication
Event	AAAI Conference on Artificial Intelligence - Hilton New Orleans Riverside, New Orleans, United States Duration: 2 Feb 2018 → 7 Feb 2018 Conference number: 32

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence
Publisher	AAAI
ISSN (Electronic)	2374-3468

Conference

Conference	AAAI Conference on Artificial Intelligence
Abbreviated title	AAAI
Country/Territory	United States
City	New Orleans
Period	02/02/2018 → 07/02/2018

Access to Document

Cite this

@inproceedings{87cc2bec7a804bc28a40c1d83a3281e5,

title = "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.",

author = "Topi Talvitie and Juho-Kustaa Kangas and Teppo Niinim{\"a}ki and Mikko Koivisto",

year = "2018",

language = "English",

series = "Proceedings of the AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

pages = "1431--1438",

booktitle = "32nd AAAI Conference on Artificial Intelligence, AAAI 2018",

address = "United States",

note = "AAAI Conference on Artificial Intelligence, AAAI ; Conference date: 02-02-2018 Through 07-02-2018",

}

Talvitie, T, Kangas, J-K, Niinimäki, T & Koivisto, M 2018, Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo. in 32nd AAAI Conference on Artificial Intelligence, AAAI 2018. Proceedings of the AAAI Conference on Artificial Intelligence, AAAI Press, pp. 1431-1438, AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, United States, 02/02/2018. <http://hdl.handle.net/10138/298469 >

Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo. / Talvitie, Topi; Kangas, Juho-Kustaa; Niinimäki, Teppo et al.
32nd AAAI Conference on Artificial Intelligence, AAAI 2018. AAAI Press, 2018. p. 1431-1438 (Proceedings of the AAAI Conference on Artificial Intelligence).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Counting Linear Extensions in Practice

T2 - AAAI Conference on Artificial Intelligence

AU - Talvitie, Topi

AU - Kangas, Juho-Kustaa

AU - Niinimäki, Teppo

AU - Koivisto, Mikko

N1 - Conference code: 32

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85055710813

M3 - Conference article in proceedings

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 1431

EP - 1438

BT - 32nd AAAI Conference on Artificial Intelligence, AAAI 2018

PB - AAAI Press

Y2 - 2 February 2018 through 7 February 2018

ER -

Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

PADS: Privacy-aware Data Science (PADS) - Yksityisyystietoinen datatiede

Finnish centre of excellence in computational inference research

Cite this

Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Projects

PADS: Privacy-aware Data Science (PADS) - Yksityisyystietoinen datatiede

Finnish centre of excellence in computational inference research

Cite this