Name
Abstract | ||
|---|---|---|
The Lovász Local Lemma discovered by Erdős and Lovász in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, József 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1667053.1667060 | Journal of the ACM |
Keywords | DocType | Volume |
present article,recent finding,constructive variant,powerful tool,prescribed collection,parallelization,general lov,sz local lemma,general local lemma algorithmic,restrictive condition,known application,combinatorial object,constructive proof,. lovasz local lemma,lovász local lemma,parallelization.,satisfiability,lovasz local lemma | Journal | 57 |
Issue | ISSN | Citations |
2 | 0004-5411 | 137 |
PageRank | References | Authors |
5.51 | 12 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robin A. Moser | 1 | 240 | 12.51 |
| Gábor Tardos | 2 | 1261 | 140.58 |