Uma versão algorítmica do Lema Local de Lovász
Resumo
O Lema Local de Lovász (LLL) é uma ferramenta poderosa para provar a existência de objetos combinatórios que satisfazem um dado conjunto de restrições. Mais precisamente, dado uma coleção finita A de eventos “ruins”, o LLL dá condições suficientes para que a probabilidade P [∩A∈A Ā] seja positiva. Em um celebrado artigo [Moser and Tardos 2010], Moser e Tardos desenvolveram um algoritmo para encontrar eficientemente tais objetos cuja existência é garantida pelo LLL. Esse trabalho discute aplicações do LLL em problemas de combinatória e aplica o algoritmo de Moser e Tardos nesses problemas.
Referências
Erdős, P. and Lovász, L. (1975). Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets, pages 609–627. North-Holland, Amsterdam.
Haeupler, B., Saha, B., and Srinivasan, A. (2011). New constructive aspects of the Lovász local lemma. J. ACM, 58(6):Art. 28, 28.
Hind, H., Molloy, M., and Reed, B. (1997). Colouring a graph frugally. Combinatorica, 17(4):469–482.
Hind, H., Molloy, M., and Reed, B. (1999). Total coloring with ∆ + poly(log ∆) colors. SIAM J. Comput., 28(3):816–821.
Leighton, T., Maggs, B., and Richa, A. W. (1999). Fast algorithms for finding O (congestion + dilation) packet routing schedules. Combinatorica, 19(3):375–401.
Molloy, M. and Reed, B. (1999). Further algorithmic aspects of the local lemma. In STOC ’98 (Dallas, TX), pages 524–529. ACM, New York.
Moser, R. A. and Tardos, G. (2010). A constructive proof of the general Lovász local lemma. J. ACM, 57(2):Art. 11, 15pp.
Haeupler, B., Saha, B., and Srinivasan, A. (2011). New constructive aspects of the Lovász local lemma. J. ACM, 58(6):Art. 28, 28.
Hind, H., Molloy, M., and Reed, B. (1997). Colouring a graph frugally. Combinatorica, 17(4):469–482.
Hind, H., Molloy, M., and Reed, B. (1999). Total coloring with ∆ + poly(log ∆) colors. SIAM J. Comput., 28(3):816–821.
Leighton, T., Maggs, B., and Richa, A. W. (1999). Fast algorithms for finding O (congestion + dilation) packet routing schedules. Combinatorica, 19(3):375–401.
Molloy, M. and Reed, B. (1999). Further algorithmic aspects of the local lemma. In STOC ’98 (Dallas, TX), pages 524–529. ACM, New York.
Moser, R. A. and Tardos, G. (2010). A constructive proof of the general Lovász local lemma. J. ACM, 57(2):Art. 11, 15pp.
Publicado
02/07/2017
Como Citar
CAVALAR, Bruno Pasqualotto.
Uma versão algorítmica do Lema Local de Lovász. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 49-52.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2017.3189.
