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

TitleFast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part I
Publication TypeTechnical Report
Year of Publication1999
AuthorsLuby, M., & Vigoda E.
Other Numbers1159
Abstract

We consider 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. We show fast convergence of this dynamics. This paper gives the more interesting proof for triangle-free graphs. The proof for arbitrary graphs is given in a companion paper. We also prove complementary hardness of approximation results, which show that it is hard to sample from this distribution when ? > c/? for a constant c > 0.

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

ICSI Technical Report TR-99-002

Abbreviated Authors

M. Luby and E. Vigoda

ICSI Research Group

Algorithms

ICSI Publication Type

Technical Report