Uma Aproximação para o Problema de Alocação de Terminais com Capacidade

  • Lehilton L. C. Pedrosa
  • Vinícius Balbino de Souzay
DOI: https://doi.org/10.5753/etc.2017.3206

Resumo


Consideramos o Problema de Alocação de Terminais com Capacidade. Uma instância é composta de um espaço métrico V , um conjunto de demandas D V 2, um número de terminais p e uma capacidade L. Uma solução é um multiconjunto S de locais para instalar terminais com jSj p e, para cada demanda, um terminal associado de forma que nenhum deles receba mais de L demandas. O objetivo é encontrar uma solução que minimiza o maior custo de servir uma demanda através do terminal atribuído. Neste trabalho, obtemos o primeiro algoritmo de aproximação para o problema, com fator 7.

Publicado
06/07/2017
Como Citar

Selecione um Formato
PEDROSA, Lehilton L. C.; DE SOUZAY, Vinícius Balbino. Uma Aproximação para o Problema de Alocação de Terminais com Capacidade. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3206.