Publications [#10388] of Mark Huber

Papers Published

1. Mark L. Huber, A faster method for sampling independent sets, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 624-626
   (last updated on 2007/08/08)

   Abstract:
   In the hard core gas model from statistical physics, the goal is to sample from a weighted distribution of independent sets of a graph. The probability of choosing a particular independent set is proportional to a parameter k raised to the size of the independent set. Currently, a Markov chain of Dyer and Greenhill is known to be mixing over the widest ranges of k. In this paper, it is shown how to use bounding chains and coupling from the past to generate exactly random samples from the hard core gas model using the Dyer/Greenhill chain.