Counting Linear Extensions in Practice: MCMC versus Exponential Monte Carlo

Topi Laurinpoika Talvitie, Juho-Kustaa Wiljami Kangas, Teppo Mikael Niinimäki, Mikko Kalle Henrik Koivisto

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.
Alkuperäiskielienglanti
OtsikkoThirty-Second AAAI Conference on Artificial Intelligence
Sivumäärä8
JulkaisupaikkaPalo Alto, CA
KustantajaAAAI Press
Julkaisupäivä2018
Sivut1431-1438
ISBN (painettu)978-1-57735-800-8
TilaJulkaistu - 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
Tapahtuma32nd AAAI Conference on Artificial Intelligence - New Orleans, Yhdysvallat (USA)
Kesto: 2 helmikuuta 20187 helmikuuta 2018
http://www.aaai.org/Conferences/AAAI/aaai18.php

Julkaisusarja

NimiProceedings of the AAAI Conference on Artificial Intelligence
KustantajaAssociation for the Advancement of Artificial Intelligence
ISSN (painettu)2159-5399
ISSN (elektroninen)2374-3468

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä