A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix
| dc.creator | Gamarnik, David | |
| dc.creator | Katz, Dmitriy | |
| dc.date | 2007-02-02 | |
| dc.date.accessioned | 2026-07-07T07:44:30Z | |
| dc.date.available | 2026-07-07T07:44:30Z | |
| dc.description | We construct a deterministic approximation algorithm for computing a permanent of a $0,1$ $n$ by $n$ matrix to within a multiplicative factor $(1+ε)^n$, for arbitrary $ε>0$. When the graph underlying the matrix is a constant degree expander our algorithm runs in polynomial time (PTAS). In the general case the running time of the algorithm is $\exp(O(n^{2\over 3}\log^3n))$. For the class of graphs which are constant degree expanders the first result is an improvement over the best known approximation factor $e^n$ obtained in \cite{LinialSamorodnitskyWigderson}. Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph Bayati et al., and Jerrum-Vazirani decomposition method. | |
| dc.description | 8 pages | |
| dc.identifier | https://arxiv.org/abs/math/0702039 | |
| dc.identifier | http://arxiv.org/abs/math/0702039 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/123218 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A16; 05C30; 68Q17; 68Q25 | |
| dc.title | A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix | |
| dc.type | text |