FPRAS Approximation of the Matrix Permanent in Practice

2020/12/06 by Newman, James E., Vardi, Moshe Y. · 1 citation
Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Mathematical Approximation and Integration #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2012.03367

openalex publication_date 2020/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The matrix permanent belongs to the complexity class #P-Complete. It is generally believed to be computationally infeasible for large problem sizes, and significant research has been done on approximation algorithms for the matrix permanent. We present an implementation and detailed runtime analysis of one such Markov Chain Monte Carlo (MCMC) based Fully Polynomial Randomized Approximation Scheme (FPRAS) for the matrix permanent, which has previously only been described theoretically and with big-Oh runtime analysis. We demonstrate by analysis and experiment that the constant factors hidden by previous big-Oh analyses result in computational infeasibility.

Cited by

• Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation

Related

• Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler
• Approximating the Permanent of a Random Matrix with Vanishing Mean
• An Adaptive Sequential Monte Carlo Algorithm for Computing Permanents
• Optimizing and benchmarking the computation of the permanent of general matrices
• Approximating the Permanent with Deep Rejection Sampling