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. 681–689.

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(n⁷(log n)⁴). 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(n⁴ log n) expected running time.