Arredondamento de PL para o Problema de Localização de Instalações Balanceado

• Lehilton Lelis Chaves Pedrosa Unicamp

DOI: https://doi.org/10.5753/etc.2023.230881

Abstract

No problema de localização de instalações, recebemos um espaço métrico contendo um conjunto de clientes e um conjunto de localizações, cada uma associada a um custo de abertura de instalação. O problema é escolher um subconjunto de localizações para abrir instalações de forma a minimizar o custo de abertura mais o custo de conectar cada cliente a alguma instalação aberta. Na versão balanceada do problema, cada cliente pode ser vermelho ou azul e só consideramos soluções em que o conjunto de clientes associado a cada instalação tenha tantos clientes vermelhos quantos azuis. Neste resumo, discutimos estratégias para construir algoritmos de aproximação para o problema utilizando arredondamento de PL.

References

Benedito, M. P. and Pedrosa, L. L. (2019). Approximation algorithms for median hub location problems. Journal of Combinatorial Optimization, pages 1–27.

Byrka, J. and Aardal, K. (2010). An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput., 39:2212–2231.

Chakrabarty, D., Goyal, P., and Krishnaswamy, R. (2020). The non-uniform k-center problem. ACM Transactions on Algorithms, 16(4):1–19.

Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. (2017). Fair clustering through fairlets. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.

Li, S. (2013). A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222(0):45–58.

Lin, J. and Vitter, J. S. (1992). ϵ-approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 771–782.