Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/76159| Tipo: | Dissertação |
| Título: | Uma extensão do lema local de Lovász e suas aplicações em programação inteira |
| Título(s) alternativo(s): | An extension of Lovász's local lemma and its applications in integer programming |
| Autor(es): | Alfonso Enrique Oré Rosales |
| Primeiro Orientador: | Bhalchandra Digambar Thatte |
| Segundo Orientador: | Maurício de Lemos Rodrigues Collares Neto |
| Primeiro membro da banca : | Aldo Procacci |
| Segundo membro da banca: | 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 |
| Idioma: | por |
| País: | Brasil |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Instituição: | UFMG |
| Departamento: | ICX - DEPARTAMENTO DE MATEMÁTICA |
| Curso: | Programa de Pós-Graduação em Matemática |
| Tipo de Acesso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/76159 |
| Data do documento: | 10-Dez-2019 |
| Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| Disertação_Mestrado_Version_Final.pdf | 1.02 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.