A Scalable Scheme for Counting Linear Extensions
Abstract
Counting the linear extensions of a given partial order not only has several applications in artificial intelligence but also represents a hard problem that challenges modern paradigms for approximate counting. Recently, Talvitie et al. (AAAI 2018) showed that an exponential time scheme beats the fastest known polynomial time schemes in practice, even if allowing hours of running time. Here, we present a novel scheme, relaxation Tootsie Pop, which in our experiments exhibits polynomial characteristics and significantly outperforms previous schemes. We also instantiate state-of-the-art model counters for CNF formulas; two natural encodings yield schemes that, however, are inferior to the more specialized schemes.
Cite
Text
Talvitie et al. "A Scalable Scheme for Counting Linear Extensions." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/710Markdown
[Talvitie et al. "A Scalable Scheme for Counting Linear Extensions." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/talvitie2018ijcai-scalable/) doi:10.24963/IJCAI.2018/710BibTeX
@inproceedings{talvitie2018ijcai-scalable,
title = {{A Scalable Scheme for Counting Linear Extensions}},
author = {Talvitie, Topi and Kangas, Kustaa and Niinimäki, Teppo Mikael and Koivisto, Mikko},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {5119-5125},
doi = {10.24963/IJCAI.2018/710},
url = {https://mlanthology.org/ijcai/2018/talvitie2018ijcai-scalable/}
}