Math @ Duke

Publications [#70394] of Mark Huber
Papers Published
 M. Huber, Exact Sampling and Approximate Counting Techniques,
Proc. 30th ACM Symposium on Theory of Computing
(1998),
pp. 3140
(last updated on 2007/08/08)
Author's Comments: Acceptance rate: 75 out of 169 papers submitted
Abstract: We present two algorithms for uniformly sampling from the proper colorings of a graph using k colors. We use exact sampling from the stationary distribution of a Markov chain with states that are the kcolorings of a graph with maximum degree Delta. As opposed to approximate sampling algorithms based on rapid mixing, these algorithms have termination criteria that allow them to stop on some inputs much more quickly than in the worst case running time bound. For the first algorithm we show that when k > Delta*(Delta + 2), the algorithm has an upper limit on the expected running time that is polynomial. For the second algorithm we show that for k > r*Delta, where r is an integer that satisfies r^r > n, the running time is polynomial. Previously, Jerrum showed that it was possible to approximately sample uniformly in polynomial time from the set of kcolorings when k >= 2*Delta, but our algorithm is the first polynomial time exact sampling algorithm for this problem. Using aprpoximate sampling, Jerrum also showed how to approximately count the number of kcolorings. We give a new procedure for approximately counting the number of kcolorings that improves the running time of the procedure of Jerrum by a factor of (m/n)^2 when k >= 2*Delta, where n is the number of nodes in the graph to be colored and m is the number of edges. In addition, we present an improved analysis of the chain of Luby and Vigoda for exact sampling from the independent sets of a graph. Finally, we present the first polynomial time method for exactly sampling from the sink free orientations of a graph. Bubley and Dyer showed how to approximately sample from this state space in Theta(m^3 ln (epsilon^(1)) time, our algorithms takes O(m^4) expected time.


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

