Papers Accepted
Abstract:
Approximation of the permanent of a matrix with nonnegative entries is a well studied problem. The most successful approach to date for general matrices uses Markov chains to approximately sample from a distribution on weighted permuations, and Jerrum, Sinclair, and Vigoda developed such a method they proved runs in polynomial time in the input. The current bound on the running time of their method is O(n^7(ln n)^4). Here we present a very different approach using sequential acceptance/rejection, and show that for a class of very dense problems, this method has an O(n^4 ln n) running time. In the process we prove a more general form of Bregman's theorem that applies not just to 0-1 matrices, but ot any matrix with entries in [0,1].