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.

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.