Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/76159| Type: | Dissertação |
| Title: | Uma extensão do lema local de Lovász e suas aplicações em programação inteira |
| Other Titles: | An extension of Lovász's local lemma and its applications in integer programming |
| Authors: | Alfonso Enrique Oré Rosales |
| First Advisor: | Bhalchandra Digambar Thatte |
| metadata.dc.contributor.advisor2: | Maurício de Lemos Rodrigues Collares Neto |
| First Referee: | Aldo Procacci |
| Second Referee: | Sokol Ndreca |
| Abstract: | 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. |
| Subject: | 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 |
| language: | por |
| metadata.dc.publisher.country: | Brasil |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE MATEMÁTICA |
| metadata.dc.publisher.program: | Programa de Pós-Graduação em Matemática |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/76159 |
| Issue Date: | 10-Dec-2019 |
| Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Disertação_Mestrado_Version_Final.pdf | 1.02 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.