Uma extensão do lema local de Lovász e suas aplicações em programação inteira

Detalhes bibliográficos
Ano de defesa:	2019
Autor(a) principal:	Alfonso Enrique Oré Rosales
Orientador(a):	Não Informado pela instituição
Banca de defesa:	Não Informado pela instituição
Tipo de documento:	Dissertação
Tipo de acesso:	Acesso aberto
Idioma:	por
Instituição de defesa:	Universidade Federal de Minas Gerais Brasil ICX - DEPARTAMENTO DE MATEMÁTICA Programa de Pós-Graduação em Matemática UFMG
Programa de Pós-Graduação:	Não Informado pela instituição
Departamento:	Não Informado pela instituição
País:	Não Informado pela instituição
Palavras-chave em Português:	Lema Local de Lóvasz algoritmos de aproximação programação inteira relaxações lineares Matemática - Teses Programação inteira – Teses Métodos de relaxação (Matemática) – Teses Algoritmos de aproximação – Teses Verificação probabilística de modelos - Teses
Link de acesso:	http://hdl.handle.net/1843/76159
Resumo:	The Lovász Local Lemma (LLL) presented by László Lovász and Paul Erdős is a very useful tool for applications of probabilistic methods. We will present an extension of the lemma, weakening the hypothesis of event dependence. As an application we consider two types of Integer Programming problems: Minimax Problems and Covering Problems, developing a fundamental technique, the random rounding of linear relaxations, to obtain good approximation algorithms for these problems.

Registros relacionados