A Faster Practical Approximation Scheme for the Permanent
DOI:
https://doi.org/10.1609/aaai.v37i10.26440Keywords:
RU: Stochastic Models & Probabilistic Inference, CSO: Search, SO: Evaluation and Analysis, SO: Sampling/Simulation-Based SearchAbstract
The permanent of a matrix has numerous applications but is notoriously hard to compute. While nonnegative matrices admit polynomial approximation schemes based on rapidly mixing Markov chains, the known practical estimators of the permanent rely on importance or rejection sampling. We advance the rejection sampling approach, which provides probabilistic accuracy guarantees, unlike importance sampling. Specifically, we give a novel class of nesting upper bounds and a simple preprocessing method that, in comparison to previous works, enable faster sampling with better acceptance rate; we demonstrate order-of-magnitude improvements with both theoretical and empirical analyses. In addition, we display instances on which our approximation scheme is competitive against state-of-the-art importance sampling based estimators.Downloads
Published
2023-06-26
How to Cite
Harviainen, J., & Koivisto, M. (2023). A Faster Practical Approximation Scheme for the Permanent. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 12216-12224. https://doi.org/10.1609/aaai.v37i10.26440
Issue
Section
AAAI Technical Track on Reasoning Under Uncertainty