Math @ Duke

Publications [#146748] of Mark Huber
Papers Published
 M. Huber and J. Law, Fast approximation of the permanent for very dense problems,
in Proceedings of the nineteenth annual ACMSIAM Symposium on Discrete Algorithms
(2008),
pp. 681689, 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 01 matrices, but ot any matrix with entries in [0,1].


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

