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

We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary n × n matrix with nonnegative entries. This algorithm---technically a "fully-polynomial randomized approximation scheme"---computes an approximation that is, with high probability, within arbitra...

Полное описание

Библиографические подробности

Опубликовано в::	Journal of the ACM 51, 4 (2004).
Главный автор:	Jerrum, Mark
Формат:	Статья
Язык:	English
Предметы:	Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Mathematics of computing. Probability and statistics. Markov processes. Probabilistic algorithms (including Monte Carlo). Algorithms. Theory.