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, ENS Paris - École normale supérieure - Paris, 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.
Type de document :
Communication dans un congrès
2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems , Jun 2015, Portland, United States. ACM, 43 (1), pp.461-462, 2015, ACM SIGMETRICS Performance Evaluation Review. 〈10.1145/2745844.2745893〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01251432
Contributeur : Ana Busic <>
Soumis le : mercredi 6 janvier 2016 - 11:08:55
Dernière modification le : jeudi 11 janvier 2018 - 06:25:34

Identifiants

Collections

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. ACM, 43 (1), pp.461-462, 2015, ACM SIGMETRICS Performance Evaluation Review. 〈10.1145/2745844.2745893〉. 〈hal-01251432〉

Partager

Métriques

Consultations de la notice

203