Uma extensão do lema local de Lovász e suas aplicações em programação inteira
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
An extension of Lovász's local lemma and its applications in integer programming
Primeiro orientador
Membros da banca
Aldo Procacci
Sokol Ndreca
Sokol Ndreca
Resumo
O Lema Local de Lovász (LLL) apresentado por László Lovász e Paul Erdős é uma ferramentamuito útil para aplicações em métodos probabilísticos. Apresentaremos uma extensão desselema, enfraquecendo a hipótese de dependência de eventos. Como aplicação consideramos doistipos de problemas de Programação Inteira: Problemas Minimax e problemas de Cobertura,desenvolvendo uma técnica fundamental, o arredondamento aleatório de relaxações lineares, paraobter bons algoritmos de aproximação para esses problemas.
Abstract
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.
Assunto
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
Palavras-chave
Lema Local de Lóvasz, algoritmos de aproximação, programação inteira, relaxações lineares