Journal
JOURNAL OF THE ACM
Volume 57, Issue 2, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1667053.1667060
Keywords
Algorithms; Constructive proof; Lovasz local lemma; parallelization
Categories
Funding
- SNF [200021-118001/1]
- NSERC [329527]
- OTKA [T-046234, AT-048826, NK-62321]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available