Two simplified versions of Red-Blue Facility Location
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.
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.