Math @ Duke

Publications [#47823] of Mark Huber
Papers Published
 M. Huber, Exact sampling from perfect matchings in dense regular graphs,
Algorithmica, vol. 44
(2006),
pp. 183193, Springer Science+Business Media, Inc.
(last updated on 2007/08/05)
Abstract: e present the first algorithm for generating random variates exactly uniformly from the set of perfect matchings of a bipartite graph with a polynomial expected running time over a nontrivial set of graphs. Previous Markov chain results obtain approximately uniform variates for arbitrary graphs in polynomial time, but their running time is Θ(n^10 (ln n)^2). Other algorithms (such as Kasteleyn's O(n^3) algorithm for planar graphs) concentrated on restricted versions of the problem. Our algorithm employs acceptance/rejection together with a new upper limit on the permanent of a form similar to Bregman's theorem. For graphs with 2n nodes, where the degree of every node is γn for a constant γ, the expected running time is O(n^{1.5 + .5/γ}). Under these conditions, Jerrum and Sinclair showed that a Markov chain of Broder can generate approximately uniform variates in Θ(n^{4.5 + .5 / γ} ln n) time, making our algorithm significantly faster on this class of graphs. The problem of counting the number of perfect matchings in these types of graphs is #P complete. In addition, we give a 1 + σ approximation algorithm for finding the permanent of 01 matrices with identical row and column sumns that runs in &O(n^{1.5 + .5/γ} (1 / σ^2) ln (1 / σ)) time, where the probability that the output is within 1 + σ of the permanent is at least 1  &delta.


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

