Geodesic
Moser–Tardos resampling algorithm, entropy compression method and the subset gas
Annales de l’Institut Henri Poincaré D, Tome 9 (2022) no. 3, pp. 435-471.

Voir la notice de l'article provenant de la source Numdam

Le texte intégral des articles récents est réservé aux abonnés de la revue. Consultez l'article sur le site de la revue.

We establish a connection between the entropy compression method and the Moser–Tardos algorithmic version of the Lovász local lemma through the cluster expansion of the subset gas. We also show that the Moser–Tardos resampling algorithm and the entropy compression bactracking algorithm produce identical bounds.

Accepté le :
Publié le :
DOI : 10.4171/aihpd/122
Classification : 05-XX, 68-XX, 82-XX
Keywords: Lovász local lemma, abstract polymer system, Moser–Tardos algorithm, entropy compression. subset gas 
@article{AIHPD_2022__9_3_435_0,
     author = {Fialho, Paula and de Lima, Bernardo and Procacci, Aldo},
     title = {Moser{\textendash}Tardos resampling algorithm, entropy compression method and the subset gas},
     journal = {Annales de l{\textquoteright}Institut Henri Poincar\'e D},
     pages = {435--471},
     volume = {9},
     number = {3},
     year = {2022},
     doi = {10.4171/aihpd/122},
     mrnumber = {4526318},
     zbl = {1508.60009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/aihpd/122/}
}
TY  - JOUR
AU  - Fialho, Paula
AU  - de Lima, Bernardo
AU  - Procacci, Aldo
TI  - Moser–Tardos resampling algorithm, entropy compression method and the subset gas
JO  - Annales de l’Institut Henri Poincaré D
PY  - 2022
SP  - 435
EP  - 471
VL  - 9
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4171/aihpd/122/
DO  - 10.4171/aihpd/122
LA  - en
ID  - AIHPD_2022__9_3_435_0
ER  - 
%0 Journal Article
%A Fialho, Paula
%A de Lima, Bernardo
%A Procacci, Aldo
%T Moser–Tardos resampling algorithm, entropy compression method and the subset gas
%J Annales de l’Institut Henri Poincaré D
%D 2022
%P 435-471
%V 9
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4171/aihpd/122/
%R 10.4171/aihpd/122
%G en
%F AIHPD_2022__9_3_435_0
Fialho, Paula; de Lima, Bernardo; Procacci, Aldo. Moser–Tardos resampling algorithm, entropy compression method and the subset gas. Annales de l’Institut Henri Poincaré D, Tome 9 (2022) no. 3, pp. 435-471. doi : 10.4171/aihpd/122. http://geodesic.mathdoc.fr/articles/10.4171/aihpd/122/

Cité par Sources :