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

• Lehilton L. C. Pedrosa UNICAMP
• Vinícius Balbino de Souza UNICAMP

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², 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.

Referências

Hochbaum, D. S. and Shmoys, D. B. (1986). A Unified Approach to Approximation Algorithms for Bottleneck Problems. J. ACM, 33(3):533–550.

Iwasa, M., Saito, H., and Matsui, T. (2009). Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems. Discrete Applied Mathematics, 157(9):2078–2088.

Khuller, S. and Sussmann, Y. J. (2000). The CapacitatedK-Center Problem. SIAM Journal on Discrete Mathematics, 13(3):403–418.

Pedrosa, L. L. C., Santos, V. F., and Schouery, R. C. S. (2016). Uma aproximação para o problema de alocação de terminais. In Anais do CSBC 2016 (1º ETC - 2016).