Publications [#70710] of Mark Huber
Papers Accepted
- M. Huber and J. Law. "Fast approximation of the permanent for very dense problems." SODA 2008 (2007).
(last updated on 2007/09/10)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].