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 language | English |
---|---|
Title of host publication | Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) |
Editors | Carles Sierra |
Publisher | IJCAI |
Pages | 524-530 |
ISBN (Electronic) | 978-0-9992411-0-3 |
DOIs | |
Publication status | Published - 2017 |
MoE publication type | A4 Conference publication |
Event | International Joint Conference on Artificial Intelligence - Melbourne, Australia Duration: 19 Aug 2017 → 25 Aug 2017 Conference number: 26 http://ijcai-17.org |
Conference
Conference | International Joint Conference on Artificial Intelligence |
---|---|
Abbreviated title | IJCAI |
Country/Territory | Australia |
City | Melbourne |
Period | 19/08/2017 → 25/08/2017 |
Internet address |
Keywords
- Combinatorial & Heuristic Search
- Evaluation and Analysis
- Uncertainty in AI
- Approximate Probabilistic Inference