论文标题
实践中矩阵永久的FPRAS近似
FPRAS Approximation of the Matrix Permanent in Practice
论文作者
论文摘要
矩阵永久属于复杂性类＃p-Complete。通常认为，对于大型问题大小，它在计算上是不可行的，并且已经对矩阵永久性的近似算法进行了重大研究。我们提供了基于Markov Carlo（MCMC）的一个这样的实施和详细的运行时分析，基于矩阵永久性的完全多项式随机近似方案（FPRA），以前仅在理论上和大OH运行时分析中对此进行了描述。我们通过分析和实验证明，先前的BIG-OH分析隐藏的常数因素导致计算不可行。
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.
