Mark Huber Publications

A faster method for sampling independent sets
M. L. Huber, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 624626.

Abstract: The problem of finding a random independent set arises in several contexts. In statistical physics, it is known as the hard core gas model. These samples may also be used to approximate the number of independent sets in a graph or to find large independent sets. One sampling approach is to run a Markov chain "for a long time". One such chain for this problem was introduced by Dyer and Greenhill, and here we develop a bounding chain for the Dyer-Greenhill chain. This bounding chain allows us to develop experimental upper bounds on the mixing time of the chain, and to create perfect samples using this chain. An implementation of this algorithm shows that on the two dimensional lattice it i faster than a competing chain, the single-site heat bath chain.


This site supported by NSF CAREER grant DMS-05-48153. Last update: 04 December 2009. Note: All downloads provided solely for use within the restrictions of the Fair Use Act, and all copyrights remain with their respective owners.