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).
Previous | Index | Next An error occured whilst processing this directive