Home
 

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