A constructive proof of the general Lovasz Local Lemma

Simple item page
dc.creatorMoser, Robin A.
dc.creatorTardos, Gábor
dc.date2009-03-03
dc.date2009-05-20
dc.date.accessioned2026-07-07T13:16:21Z
dc.date.available2026-07-07T13:16:21Z
dc.descriptionThe 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.
dc.description8 pages
dc.identifierhttps://arxiv.org/abs/0903.0544
dc.identifierhttp://arxiv.org/abs/0903.0544
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/230760
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.titleA constructive proof of the general Lovasz Local Lemma
dc.typetext

Files

Collections

arXiv