ملخص: Abstract. The Lovasz Local Lemma discovered by Erd?os 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, J´ozsef 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.

لغة: إنجليزية
الموضوع الإعلام الآلي

الكلمات الدالة:
Constructive proof
Lovasz local lemma
parallelization