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

Página do item simplificado
dc.creatorAlfonso Enrique Oré Rosales
dc.date.accessioned2024-09-10T16:24:21Z
dc.date.accessioned2025-09-08T23:08:17Z
dc.date.available2024-09-10T16:24:21Z
dc.date.issued2019-12-10
dc.description.abstractThe 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.
dc.description.sponsorshipCAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
dc.identifier.urihttps://hdl.handle.net/1843/76159
dc.languagepor
dc.publisherUniversidade Federal de Minas Gerais
dc.rightsAcesso Aberto
dc.subjectMatemática - Teses
dc.subjectProgramação inteira – Teses
dc.subjectMétodos de relaxação (Matemática) – Teses
dc.subjectAlgoritmos de aproximação – Teses
dc.subjectVerificação probabilística de modelos - Teses
dc.subject.otherLema Local de Lóvasz
dc.subject.otheralgoritmos de aproximação
dc.subject.otherprogramação inteira
dc.subject.otherrelaxações lineares
dc.titleUma extensão do lema local de Lovász e suas aplicações em programação inteira
dc.title.alternativeAn extension of Lovász's local lemma and its applications in integer programming
dc.typeDissertação de mestrado
local.contributor.advisor-co1Maurício de Lemos Rodrigues Collares Neto
local.contributor.advisor-co1Latteshttp://lattes.cnpq.br/9400871572268469
local.contributor.advisor1Bhalchandra Digambar Thatte
local.contributor.advisor1Latteshttp://lattes.cnpq.br/5544298698489595
local.contributor.referee1Aldo Procacci
local.contributor.referee1Sokol Ndreca
local.creator.Latteshttp://lattes.cnpq.br/9757117947905931
local.description.resumoO 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.
local.publisher.countryBrasil
local.publisher.departmentICX - DEPARTAMENTO DE MATEMÁTICA
local.publisher.initialsUFMG
local.publisher.programPrograma de Pós-Graduação em Matemática

Arquivos

Pacote original

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Disertação_Mestrado_Version_Final.pdf
Tamanho:
1015.96 KB
Formato:
Adobe Portable Document Format
Baixar

Licença do pacote

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
license.txt
Tamanho:
2.07 KB
Formato:
Plain Text
Descrição:
Baixar

Coleções

Pós-Graduação em Matemática - Dissertações

Logo UFMG