A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix

Details A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix

2007-02-02

arxiv.org/abs/math/0702039v1

Mathematics

Combinatorics

8 pages

Scientific paper

We construct a deterministic approximation algorithm for computing a permanent of a $0,1$ $n$ by $n$ matrix to within a multiplicative factor $(1+\epsilon)^n$, for arbitrary $\epsilon>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.

Affiliated with

Also associated with

No associations

Rating

A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-676059