Arredondamento Aleatorizado para o Problema de Localização de Instalações Justo

• Jovânio José Galvão Júnior Unicamp
• Lehilton Lelis Chaves Pedrosa Unicamp

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

Resumo

No Problema de Localização de Instalações sob o critério de justiça min-max (UFLP Justo), o objetivo é selecionar um conjunto de instalações e associar cada cliente a uma instalação de forma a minimizar o máximo custo médio de conexão entre grupos mais o custo normalizado de instalações. Adaptamos um algoritmo clássico de arredondamento para o UFLP e mostramos que ele é α-fiel em expectativa, com α ≈ 1,3737. Combinando essa cota por cliente com o custo esperado de abertura, obtemos uma 1,6774-aproximação aleatorizada, enquanto o melhor algoritmo conhecido é uma 4-aproximação determinística.

Referências

Abbasi, M., Bhaskara, A., and Venkatasubramanian, S. (2021). Fair clustering via equitable group representations. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pages 504–514.

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

Lin, J.-H. and Vitter, J. S. (1992). ϵ-Approximations with Minimum Packing Constraint Violation (Extended Abstract). In Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing, STOC ’92, pages 771–782, New York, NY, USA. ACM.

Vazirani, V. V. (2001). Approximation algorithms, volume 1. Springer.

Williamson, D. P. and Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge university press.