Thumbnail
Access Restriction
Subscribed

Author Jerrum, Mark ♦ Sinclair, Alistair ♦ Vigoda, Eric
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2004
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Markov chain Monte Carlo ♦ Permanent of a matrix ♦ Rapidly mixing Markov chains
Abstract We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary $\textit{n}$ × $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2004-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 51
Issue Number 4
Page Count 27
Starting Page 671
Ending Page 697


Open content in new tab

   Open content in new tab
Source: ACM Digital Library