Back to Search
Start Over
A deterministic approximation algorithm for computing the permanent of a matrix
- Source :
-
Journal of Computer & System Sciences . Dec2010, Vol. 76 Issue 8, p879-883. 5p. - Publication Year :
- 2010
-
Abstract
- Abstract: We consider the problem of computing the permanent of a n by n matrix. For a class of matrices corresponding to constant degree expanders we construct a deterministic polynomial time approximation algorithm to within a multiplicative factor , for arbitrary . This is an improvement over the best known approximation factor obtained in Linial, Samorodnitsky and Wigderson (2000) , though the latter result was established for arbitrary non-negative matrices. Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph (Bayati, Gamarnik, Katz, Nair and Tetali (2007) ) and Jerrum–Vazirani method (Jerrum and Vazirani (1996) ) of approximating permanent by near perfect matchings. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 76
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 53318159
- Full Text :
- https://doi.org/10.1016/j.jcss.2010.05.002