A Meeting Point of Probability, Graphs, and Algorithms: The Lovász Local Lemma and Related Results—A Survey

Autor:	András Faragó
Jazyk:	angličtina
Rok vydání:	2021
Předmět:	Lovász Local Lemma probabilistic method in combinatorics probabilistic polynomial time algorithm Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95
Zdroj:	Algorithms, Vol 14, Iss 12, p 355 (2021)
Druh dokumentu:	article
ISSN:	1999-4893
DOI:	10.3390/a14120355
Popis:	A classic and fundamental result, known as the Lovász Local Lemma, is a gem in the probabilistic method of combinatorics. At a high level, its core message can be described by the claim that weakly dependent events behave similarly to independent ones. A fascinating feature of this result is that even though it is a purely probabilistic statement, it provides a valuable and versatile tool for proving completely deterministic theorems. The Lovász Local Lemma has found many applications; despite being originally published in 1973, it still attracts active novel research. In this survey paper, we review various forms of the Lemma, as well as some related results and applications.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/8c5dc1d8c124437bb461b71a8b36c937 Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.