Publications [#146748] of Mark Huber

Papers Published

1. M. Huber and J. Law, Fast approximation of the permanent for very dense problems, in Proceedings of the nineteenth annual ACM-SIAM Symposium on Discrete Algorithms (2008), pp. 681--689, SIAM, Philadelphia, PA, USA
   (last updated on 2008/06/16)

   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].