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