Two simplified versions of Red-Blue Facility Location
Resumo
The Red-Blue Facility Location problem is a generalization of Facility Location where clients may have two types of demands and each open facility must provide for one of the types of demands. We present preliminary results for two special cases of this problem.
Palavras-chave:
Red-Blue, Facility Location Problem
Referências
Arora, S., Gupta, N., Khuller, S., Sabharwal, Y., and Singhal, S. (2014). Facility location with red-blue demands. Oper. Res. Lett., 42(6):462–465.
Baev, I., Rajaraman, R., and Swamy, C. (2008). Approximation algorithms for data place- ment problems. SIAM J. Comput., 38(4):1411–1429.
Guha, S. and Khuller, S. (1999). Greedy strikes back: Improved facility location algo- rithms. Journal ofAlgorithms, 31(1):228 – 248.
Hajiaghayi, M., Khandekar, R., and Kortsarz, G. (2010). Budgeted red-blue median and its generalizations. In Proceedings of the 18th Annual European Conference on Algo- rithms: Part I, ESA’10, pages 314–325, Berlin, Heidelberg. Springer-Verlag.
Hochbaum, D. S. (1982). Heuristics for the fixed cost median problem. Math. Program., 22(1):148–162.
Li, S. (2013). A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45–58.
Swamy, C. (2016). Improved approximation algorithms for matroid and knapsack median problems and applications. ACMTransactions on Algorithms, 12(4). Article 49.
Baev, I., Rajaraman, R., and Swamy, C. (2008). Approximation algorithms for data place- ment problems. SIAM J. Comput., 38(4):1411–1429.
Guha, S. and Khuller, S. (1999). Greedy strikes back: Improved facility location algo- rithms. Journal ofAlgorithms, 31(1):228 – 248.
Hajiaghayi, M., Khandekar, R., and Kortsarz, G. (2010). Budgeted red-blue median and its generalizations. In Proceedings of the 18th Annual European Conference on Algo- rithms: Part I, ESA’10, pages 314–325, Berlin, Heidelberg. Springer-Verlag.
Hochbaum, D. S. (1982). Heuristics for the fixed cost median problem. Math. Program., 22(1):148–162.
Li, S. (2013). A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45–58.
Swamy, C. (2016). Improved approximation algorithms for matroid and knapsack median problems and applications. ACMTransactions on Algorithms, 12(4). Article 49.
Publicado
02/07/2019
Como Citar
FERNANDES, Cristina; POCAI, Rafael .
Two simplified versions of Red-Blue Facility Location. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 4. , 2019, Belém.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2019.6391.
