Math @ Duke

Publications [#10388] of Mark Huber
Papers Published
 Mark L. Huber, A faster method for sampling independent sets,
Proceedings of the 11th Annual ACMSIAM Symposium on Discrete Algorithms
(2000),
pp. 624626
(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.


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

