The Mixing of Markov Chains on Linear Extensions in Practice

Topi Talvitie, Teppo Niinimäki, Mikko Koivisto

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


We investigate almost uniform sampling from the set of linear extensions of a given partial order. The most efficient schemes stem from Markov chains whose mixing time bounds are polynomial, yet impractically large. We show that, on instances one encounters in practice, the actual mixing times can be much smaller than the worst-case bounds, and particularly so for a novel Markov chain we put forward. We circumvent the inherent hardness of estimating standard mixing times by introducing a refined notion, which admits estimation for moderate-size partial orders. Our empirical results suggest that the Markov chain approach to sample linear extensions can be made to scale well in practice, provided that the actual mixing times can be realized by instance-sensitive bounds or termination rules. Examples of the latter include existing perfect simulation algorithms, whose running times in our experiments follow the actual mixing times of certain chains, albeit with significant overhead.
OtsikkoProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
KustantajaInternational Joint Conferences on Artificial Intelligence
ISBN (elektroninen)978-0-9992411-0-3
DOI - pysyväislinkit
TilaJulkaistu - 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Joint Conferences on Artificial Intelligence - Melbourne, Australia
Kesto: 19 elokuuta 201725 elokuuta 2017
Konferenssinumero: 28


  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä