






















The Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Bec91], Beck demonstrated that a constructive variant can be given under certain more restrictive conditions. Simplifications of his procedure and relaxations of its restrictions were subsequently exhibited in several publications [Alo91, MR98, CS00, Mos06, Sri08, Mos08]. In [Mos09], a constructive proof was presented that works under negligible restrictions, formulated in terms of the Bounded Occurrence Satisfiability problem. In the present paper, we reformulate and improve upon these findings so as to directly apply to almost all known applications of the general Local Lemma.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。