## A Mildly Exponential Approximation Algorithm for the
Permanent

**Mark Jerrum and Umesh Vazirani**
*Abstract:* A new approximation algorithm for the permanent
of an *n* x *n* 0,1-matrix is presented. The algorithm is
shown to have worst-case time complexity exp(O(n^1/2log^2n)).
Asymptotically, this represents a considerable improvement over the
best existing algorithm, which has worst-case time complexity of
the form e^(n).

*LFCS report ECS-LFCS-91-179*

Previous |

Index |

Next