Uma Aproximação para o Problema de Alocação de Terminais com Capacidade - Pedrosa, Lehilton L. C.; de Souza, Vinícius Balbino (Anais do Encontro de Teoria da Computação (ETC), 2017)
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 |S| ≤ p, 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.