Geodesic
A note on the Glauber dynamics for sampling independent sets
The electronic journal of combinatorics, Tome 8 (2001) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

This note considers the problem of sampling from the set of weighted independent sets of a graph with maximum degree $\Delta$. For a positive fugacity $\lambda$, the weight of an independent set $\sigma$ is $\lambda^{|\sigma|}$. Luby and Vigoda proved that the Glauber dynamics, which only changes the configuration at a randomly chosen vertex in each step, has mixing time $O(n\log{n})$ when $\lambda < {{2}\over {\Delta-2}}$ for triangle-free graphs. We extend their approach to general graphs.
DOI : 10.37236/1552
Classification : 68W20, 60J10
Mots-clés : sampling, Glauber dynamics 
@article{10_37236_1552,
     author = {Eric Vigoda},
     title = {A note on the {Glauber} dynamics for sampling independent sets},
     journal = {The electronic journal of combinatorics},
     year = {2001},
     volume = {8},
     number = {1},
     doi = {10.37236/1552},
     zbl = {0967.68172},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1552/}
}
TY  - JOUR
AU  - Eric Vigoda
TI  - A note on the Glauber dynamics for sampling independent sets
JO  - The electronic journal of combinatorics
PY  - 2001
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1552/
DO  - 10.37236/1552
ID  - 10_37236_1552
ER  - 
%0 Journal Article
%A Eric Vigoda
%T A note on the Glauber dynamics for sampling independent sets
%J The electronic journal of combinatorics
%D 2001
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1552/
%R 10.37236/1552
%F 10_37236_1552
Eric Vigoda. A note on the Glauber dynamics for sampling independent sets. The electronic journal of combinatorics, Tome 8 (2001) no. 1. doi: 10.37236/1552

Cité par Sources :