Mark Huber Publications

Fast approximation of the permanent for very dense problems
M. Huber and J. Law, Proc. of Symposium on Discrete Algorithms (2008), pp. 681689.

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 permutations, 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(n7(log n)4). Here we present a very different approach using sequential acceptance/rejection, and show that for a class of dense problems this method has an O(n4 log n) expected running time.


This site supported by NSF CAREER grant DMS-05-48153. Last update: 04 December 2009. Note: All downloads provided solely for use within the restrictions of the Fair Use Act, and all copyrights remain with their respective owners.