



























We study distributed versions of Markov Chain Monte Carlo (MCMC) algorithms for generating random $k$-colorings of an input graph with maximum degree $Δ$. In the sequential setting, the Glauber dynamics is the simple MCMC algorithm which updates the color at a randomly chosen vertex in each step. Fischer and Ghaffari (2018), and independently Feng, Hayes, and Yin (2018), presented a parallel and distributed version of the Glauber dynamics which converges in $O(\log{n})$ rounds for $k>(2+\varepsilon)Δ$ for any $\varepsilon>0$. We present the distributed flip dynamics and prove $O(n\log{n})$ mixing for $k>(11/6-δ)Δ$ for a fixed $δ>0$. Our new Markov chain is a generalization of the distributed Glauber dynamics previously analyzed, and is a parallel and distributed version of the more general flip dynamics considered in the sequential setting which recolors local maximal two-colored components in each step. While the distributed Glauber dynamics and the sequential flip dynamics are symmetric Markov chains, and hence their stationary distribution is uniformly distributed over colorings, our distributed flip dynamics is not symmetric and hence the stationary distribution is unclear.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。