Use este identificador para citar o ir al link de este elemento:
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 |
| primer Tutor: | Bhalchandra Digambar Thatte |
| Segundo Tutor: | Maurício de Lemos Rodrigues Collares Neto |
| primer miembro del tribunal : | Aldo Procacci |
| Segundo miembro del tribunal: | Sokol Ndreca |
| Resumen: | 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. |
| Asunto: | 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 Institución: | UFMG |
| Departamento: | ICX - DEPARTAMENTO DE MATEMÁTICA |
| Curso: | Programa de Pós-Graduação em Matemática |
| Tipo de acceso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/76159 |
| Fecha del documento: | 10-dic-2019 |
| Aparece en las colecciones: | Dissertações de Mestrado |
archivos asociados a este elemento:
| archivo | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| Disertação_Mestrado_Version_Final.pdf | 1.02 MB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.