The Online Connected Facility Location Problem

In this paper we propose the Online Connected Facility Location problem (OCFL), which is an online version of the Connected Facility Location problem (CFL). The CFL is a combination of the Uncapacitated Facility Location problem (FL) and the Steiner Tree problem (ST). We give a randomized O(log2 n)-competitive algorithm for the OCFL via the sample-and-augment framework of Gupta, Kumar, Pál, and Roughgarden and previous algorithms for Online Facility Location (OFL) and Online Steiner Tree (OST). Also, we show that the same algorithm is a deterministic O(logn)-competitive algorithm for the special case of the OCFL with M∈=∈1, where M is a scale factor for the edge costs. © 2014 Springer-Verlag Berlin Heidelberg.8392 LNCS574585Agencia Nacional de Investigacion e Innovacion (ANII),Centro Latinoamericano de Estudios en Informatica (CLEI),et al.,Google,Universidad de la Republica, CSIC,Yahoo! LabsShmoys, D.B., Approximation algorithms for facility location problems (2000) APPROX 2000. LNCS, 1913, pp. 27-32. , Jansen, K., Khuller, S. (eds.) Springer, HeidelbergMahdian, M., Ye, Y., Zhang, J., Approximation algorithms for metric facility location problems (2006) SIAM Journal on Computing, 36, pp. 411-432Byrka, J., Aardal, K., An optimal bifactor approximation algorithm for the metric facility location problem (2010) SIAM Journal on Computing, 39, pp. 2212-2231Li, S., A 1.488 approximation algorithm for the uncapacitated facility location problem (2013) Information and Computation, 222, pp. 45-58Borodin, A., El-Yaniv, R., (1998) On Line Computation and Competitive ANALYSIS, , Press Syndicate of the University of CambridgeMeyerson, A., Online facility location (2001) Proceedings of the 42nd IEEE, pp. 426-431. , Symposium on Foundations of Computer ScienceFotakis, D., On the competitive ratio for online facility location (2008) Algorithmica, 50, pp. 1-57Fotakis, D., A primal-dual algorithm for online non-uniform facility location (2007) Journal of Discrete Algorithms, 5 (1), pp. 141-148Nagarajan, C., Williamson, D.P., Offline and online facility leasing (2008) IPCO 2008. LNCS, 5035, pp. 303-315. , Lodi, A., Panconesi, A., Rinaldi, G. (eds.) Springer, HeidelbergFotakis, D., Online and incremental algorithms for facility location (2011) SIGACT News, 42 (1), pp. 97-131Vazirani, V., (2003) Approximation Algorithms, , SpringerWilliamson, D.P., Shmoys, D.B., (2011) The Design of Approximation Algorithms, , Cambridge University PressImase, M., Waxman, B.M., Dynamic Steiner tree problem (1991) SIAM Journal on Discrete Mathematics, 4 (3), pp. 369-384Buchbinder, N., Naor, J.S., The design of competitive online algorithms via a primal-dual approach (2009) Foundations and Trends in Theoretical Computer Science, 3, pp. 93-263Gupta, A., Kumar, A., Pál, M., Roughgarden, T., Approximation via cost sharing: Simpler and better approximation algorithms for network design (2007) Journal of the ACM, 54 (3). , Article 11Gupta, A., Srinivasan, A., Tardos, E., Cost-sharing mechanisms for network design (2008) Algorithmica, 50, pp. 98-119Swamy, C., Kumar, A., Primal-dual algorithms for connected facility location problems (2004) Algorithmica, 40 (4), pp. 245-269Hasan, M.K., Jung, H., Chwa, K.Y., Approximation algorithms for connected facility location (2008) Journal of Combinatorial Optimization, 16, pp. 155-172Jung, H., Hasan, M.K., Chwa, K.Y., A 6.55 factor primal-dual approximation algorithm for the connected facility location problem (2009) Journal of Combinatorial Optimization, 18, pp. 258-271Eisenbrand, F., Grandoni, F., Rothvoß, T., Schäfer, G., Connected facility location via random facility sampling and core detouring (2010) Journal of Computer and System Sciences, 76 (8), pp. 709-72