A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

被引：399

作者：

Jerrum, M

Sinclair, A

Vigoda, E

机构：

[1] Univ Edinburgh, Sch Informat, Edinburgh EH9 3JZ, Midlothian, Scotland

[2] Univ Calif Berkeley, Div Comp Sci, Berkeley, CA 94720 USA

[3] Univ Chicago, Dept Comp Sci, Chicago, IL 60637 USA

来源：

JOURNAL OF THE ACM | 2004年 / 51卷 / 04期

关键词：

Markov chain Monte Carlo; permanent of a matrix; rapidly mixing Markov chains; algorithms; theory;

D O I：

10.1145/1008731.1008738

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：671 / 697

页数：27

共 27 条

[1]

Aldous D., 1987, Probability in the Engineering and Informational Sciences, V1, P33, DOI [10.1017/S0269964800000267, DOI 10.1017/S0269964800000267]

[2]

ALON N, 1992, PROBABILISTIC METHOD

[3]

Barvinok A, 1999, RANDOM STRUCT ALGOR, V14, P29, DOI 10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO

[4]

2-X

[5]

Broder AZ, 1986, P 18 ANN ACM S THEOR, P50, DOI DOI 10.1145/12130.12136

[6]

Chien S., 2002, P 34 ANN ACM S THEOR, P222

[7]

Diaconis P., 1991, Ann. Appl. Probab., P36

[8]

Diaconis P., 1993, Ann. Appl. Probab., V3, P696, DOI [10.1214/aoap/1177005359, DOI 10.1214/AOAP/1177005359]

[9] A Chernoff bound for random walks on expander graphs [J].

Gillman, D .

SIAM JOURNAL ON COMPUTING, 1998, 27 (04) :1203-1220

[10] APPROXIMATING THE PERMANENT [J].

JERRUM, M ;

SINCLAIR, A .

SIAM JOURNAL ON COMPUTING, 1989, 18 (06) :1149-1178

← 1 2 3 →