期刊
JOURNAL OF THE ACM
卷 57, 期 2, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1667053.1667060
关键词
Algorithms; Constructive proof; Lovasz local lemma; parallelization
类别
资金
- SNF [200021-118001/1]
- NSERC [329527]
- OTKA [T-046234, AT-048826, NK-62321]
The Lovasz Local Lemma discovered by Erdos and Lovasz in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, Jozsef Beck was the first to demonstrate that a constructive variant can be given under certain more restrictive conditions, starting a whole line of research aimed at improving his algorithm's performance and relaxing its restrictions. In the present article, we improve upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据