A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
复制标题
DOI：
10.1145/1008731.1008738
复制
发表时间：
2004-07-01
影响因子：
2.5
通讯作者：
Vigoda, E
中科院分区：
文献类型：
--
作者：
Jerrum, M;Sinclair, A;Vigoda, E
提出了一种估计任意n × n非负项矩阵永久性的多项式时间随机算法。这个算法——从技术上讲是一个“全多项式随机近似方案”——计算一个近似，这个近似在任意小的指定相对误差范围内，具有很高的概率。
We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary n x n matrix with nonnegative entries. This algorithm-technically a "fully-polynomial randomized approximation scheme" - computes an approximation that is, with high probability, within arbitrarily small specified relative error of the true value of the permanent.