Problema da Deposição Gamma: Prova de NP-Completude e um Novo Modelo de Programação Linear Inteira

- 84686
Artigo Completo
Favoritar este trabalho
Como citar esse trabalho?
Resumo

A Deposição Gamma é uma métrica utilizada para avaliar a qualidade de serviço oferecida por redes veiculares. A definição do Problema da Deposição Gamma decorre diretamente do emprego dessa métrica na minimização das unidades de infraestrutura de comunicação alocadas para compor redes veiculares. Neste trabalho, apresenta-se uma prova de que a versão de decisão desse problema pertence à classe de complexidade NP-Completo. Adicionalmente, é discutida a formulação de programação linear inteira multifluxo presente na literatura e é proposta uma nova formulação, baseada em cobertura de conjuntos por vértices. Nos experimentos realizados em um resolvedor comercial, a formulação proposta apresenta resultados amplamente superiores aos obtidos com a formulação original.

Instituições
  • 1 Universidade Federal de Minas Gerais
  • 2 Centro Federal de Educação Tecnológica de Minas Gerais
Eixo Temático
  • OC – Otimização Combinatória
Palavras-chave
Deposição Gamma
NP-Completo
Programação linear inteira