The Mixing of Markov Chains on Linear Extensions in Practice

Topi Talvitie, Teppo Niinimäki, Mikko Koivisto

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

Abstract

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 upper 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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)
EditorsCarles Sierra
Pages524-530
ISBN (Electronic)978-0-9992411-0-3
DOIs
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventInternational Joint Conference on Artificial Intelligence - Melbourne, Australia
Duration: 19 Aug 201725 Aug 2017
Conference number: 26
http://ijcai-17.org

Conference

ConferenceInternational Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI
CountryAustralia
CityMelbourne
Period19/08/201725/08/2017
Internet address

Keywords

  • Combinatorial & Heuristic Search
  • Evaluation and Analysis
  • Uncertainty in AI
  • Approximate Probabilistic Inference

Fingerprint Dive into the research topics of 'The Mixing of Markov Chains on Linear Extensions in Practice'. Together they form a unique fingerprint.

  • Cite this

    Talvitie, T., Niinimäki, T., & Koivisto, M. (2017). The Mixing of Markov Chains on Linear Extensions in Practice. In C. Sierra (Ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) (pp. 524-530) https://doi.org/10.24963/ijcai.2017/74