A deterministic approximation algorithm for computing the permanent of a 0,1 matrix
| Autor: | David Gamarnik, Dmitriy Katz |
|---|---|
| Přispěvatelé: | Sloan School of Management, Gamarnik, David, Rogozhnikov, Dmitriy A. |
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
Polynomial time approximation algorithm General Computer Science Computer Networks and Communications Efficient algorithm Applied Mathematics Multiplicative function Graph Theoretical Computer Science Combinatorics Matrix (mathematics) Computational Theory and Mathematics Deterministic approximation Computing the permanent Algorithm Mathematics |
| Zdroj: | Prof. Gamarnik via Alex Caracuzzo |
| ISSN: | 0022-0000 |
| Popis: | We consider the problem of computing the permanent of a 0,1n 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 ([email protected])^n, for arbitrary @e>0. This is an improvement over the best known approximation factor e^n obtained in Linial, Samorodnitsky and Wigderson (2000) [9], 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) [2]) and Jerrum-Vazirani method (Jerrum and Vazirani (1996) [8]) of approximating permanent by near perfect matchings. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect