Speeding up Glauber Dynamics for Random Generation of Independent Sets

Rémi Varloot 1, 2 Ana Busic 2, 3 Anne Bouillard 4, 2, 3
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : The maximum independent set (MIS) problem is a well-studied combinatorial optimization problem that naturally arises in many applications, such as wireless communication, information theory and statistical mechanics. MIS problem is NP-hard, thus many results in the literature focus on fast generation of maximal independent sets of high cardinality. One possibility is to combine Gibbs sampling with coupling from the past arguments to detect convergence to the stationary regime. This results in a sampling procedure with time complexity that depends on the mixing time of the Glauber dynamics Markov chain. We propose an adaptive method for random event generation in the Glauber dynamics that considers only the events that are effective in the coupling from the past scheme, accelerating the convergence time of the Gibbs sampling algorithm.
Complete list of metadatas

https://hal.inria.fr/hal-01251432
Contributor : Ana Busic <>
Submitted on : Wednesday, January 6, 2016 - 11:08:55 AM
Last modification on : Tuesday, May 14, 2019 - 10:14:33 AM

Links full text

Identifiers

Citation

Rémi Varloot, Ana Busic, Anne Bouillard. Speeding up Glauber Dynamics for Random Generation of Independent Sets. 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems , Jun 2015, Portland, United States. pp.461-462, ⟨10.1145/2745844.2745893⟩. ⟨hal-01251432⟩

Share

Metrics

Record views

322