A MONTE-CARLO ALGORITHM FOR ESTIMATING THE PERMANENT

被引：53

作者：

KARMARKAR, N

KARP, R

LIPTON, R

LOVASZ, L

LUBY, M

机构：

[1] UNIV CALIF BERKELEY,DIV COMP SCI,BERKELEY,CA 94720

[2] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

[3] HUNGARIAN ACAD SCI,H-1051 BUDAPEST,HUNGARY

[4] INT COMP SCI INST,BERKELEY,CA 94720

来源：

SIAM JOURNAL ON COMPUTING | 1993年 / 22卷 / 02期

关键词：

PERMANENT; MATCHING; MONTE-CARLO ALGORITHM; ALGORITHM; BIPARTITE GRAPH; DETERMINANT;

D O I：

10.1137/0222021

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let A be an n x n matrix with 0-1 valued entries, and let per(A) be the permanent of A. This paper describes a Monte-Carlo algorithm that produces a ''good in the relative sense'' estimate of per(A) and has running time poly(n)2n/2, where poly(n) denotes a function that grows polynomially with n.

引用

页码：284 / 293

页数：10

共 21 条

[1] RSA AND RABIN FUNCTIONS - CERTAIN PARTS ARE AS HARD AS THE WHOLE [J].

ALEXI, W ;

CHOR, B ;

GOLDREICH, O ;

SCHNORR, CP .

SIAM JOURNAL ON COMPUTING, 1988, 17 (02) :194-209

[2]

[Anonymous], 1963, CARUS MATH MONOGRAPH

[3]

BACH E, 1987, 19TH P ANN ACM S THE, P453

[4]

BRODER AZ, 1986, 18TH P ACM S THEOR C, P50

[5]

CARTER L, 1979, J CSS, V18, P143, DOI DOI 10.1016/0022-0000(79)90044-8

[6] A MEASURE OF ASYMPTOTIC EFFICIENCY FOR TESTS OF A HYPOTHESIS BASED ON THE SUM OF OBSERVATIONS [J].

CHERNOFF, H .

ANNALS OF MATHEMATICAL STATISTICS, 1952, 23 (04) :493-507

[7]

CHOR B, IN PRESS J COMPLEXIT

[8]

FRIEZE AM, 1989, UNPUB NOTE COMPUTING

[9]

Godsil C., 1981, ALGEBRAIC METHODS GR, P241

[10] APPROXIMATING THE PERMANENT [J].

JERRUM, M ;

SINCLAIR, A .

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

← 1 2 3 →