期刊
RANDOM STRUCTURES & ALGORITHMS
卷 -, 期 -, 页码 -出版社
WILEY
DOI: 10.1002/rsa.21152
关键词
Lovasz Local Lemma; LLL; derandomization; independent transversal; strong coloring
The Lovasz local lemma guarantees the existence of configurations that avoid a collection of mostly independent bad events. The MT algorithm provides randomized algorithms for constructions based on the LLL, while deterministic algorithms have been lacking. The authors address three specific shortcomings of prior deterministic algorithms and provide applications to various problems.
The Lovasz local lemma (LLL) is a keystone principle in probability theory, guaranteeing the existence of configurations which avoid a collection B of bad events which are mostly independent and have low probability. A seminal algorithm of Moser and Tardos (J. ACM, 2010, 57, 11) (which we call the MT algorithm) gives nearly-automatic randomized algorithms for most constructions based on the LLL. However, deterministic algorithms have lagged behind. We address three specific shortcomings of the prior deterministic algorithms. First, our algorithm applies to the LLL criterion of Shearer (Combinatorica, 1985, 5, 241-245); this is more powerful than alternate LLL criteria and also leads to cleaner and more legible bounds. Second, we provide parallel algorithms with much greater flexibility. Third, we provide a derandomized version of the MT-distribution, that is, the distribution of the variables at the termination of the MT algorithm. We show applications to non-repetitive vertex coloring, independent transversals, strong coloring, and other problems.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据