Fast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part II

TitleFast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part II
Publication TypeTechnical Report
Year of Publication1999
AuthorsVigoda, E.
Other Numbers1160
Abstract

This work is a continuation of ICSI Technical Report TR-99-002. The focus is on the problem of sampling independent sets of a graph with maximum degree ?. The weight of each independent set is expressed in terms of a fixed positive parameter ? ? 2/?-2, where the weight of an independent set ? is ?|?|. The Glauber dynamics is a simple Markov chain Monte Carlo method for sampling from this distribution. In the companion work, we showed fast convergence of this dynamics for triangle-free graphs. This paper proves fast convergence for arbitrary graphs.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1999/tr-99-003.pdf
Bibliographic Notes

ICSI Technical Report TR-99-003

Abbreviated Authors

E. Vigoda

ICSI Research Group

Algorithms

ICSI Publication Type

Technical Report