Publication Details
Title: Fast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part I
Author: M. Luby and E. Vigoda
Group: ICSI Technical Reports
Date: January 1999
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1999/tr-99-002.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-99-002
Bibliographic Reference:
M. Luby and E. Vigoda. Fast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part I. ICSI Technical Report TR-99-002, January 1999
Author: M. Luby and E. Vigoda
Group: ICSI Technical Reports
Date: January 1999
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1999/tr-99-002.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-99-002
Bibliographic Reference:
M. Luby and E. Vigoda. Fast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part I. ICSI Technical Report TR-99-002, January 1999