Fast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part I
Title | Fast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part I |
Publication Type | Technical Report |
Year of Publication | 1999 |
Authors | Luby, M., & Vigoda E. |
Other Numbers | 1159 |
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. |
URL | http://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 |