Abstract
In the k-center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitated \(\alpha \) -fault-tolerant k -center, where centers have a limit on the number of assigned elements, and, if \(\alpha \) centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the \(\{0,L\}\)-capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the previously best known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming \(\alpha \) is constant, our method leads to the first approximations for this case.
Partially supported by CAPES, CNPq (grants 308523/2012-1, 477203/2012-4, and 456792/2014-7), FAPESP (grants 2013/03447-6 and 2014/14209-1), and MaCLinC.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
An, H.-C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated k-center. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 52–63. Springer, Heidelberg (2014)
Bar-Ilan, J., Kortsarz, G., Peleg, D.: How to allocate network centers. J. Algorithms 15(3), 385–415 (1993)
Chaudhuri, S., Garg, N., Ravi, R.: The \(p\)-neighbor \(k\)-center problem. Inf. Process. Lett. 65(3), 131–134 (1998)
Chechik, S., Peleg, D.: The fault-tolerant capacitated \(k\)-center problem. Theor. Comput. Sci. 566, 12–25 (2015)
Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for \(k\)-centers with non-uniform hard capacities. In: IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 273–282 (2012)
Cygan, M., Kociumaka, T.: Constant factor approximation for capacitated \(k\)-center with outliers. In: 31st International Symposium on Theoretical Aspects of ComputerScience (STACS), vol. 25, pp. 251–262 (2014)
Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC), pp. 434–444. ACM, New York (1988)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293–306 (1985)
Hall, P.: On representatives of subsets. J. London Math. Soc 10(1), 26–30 (1935)
Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the \(k\)-center problem. Math. Oper. Res. 10(2), 180–184 (1985)
Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3), 533–550 (1986)
Hsu, W.L., Nemhauser, G.L.: Easy and hard bottleneck location problems. Discrete Appl. Math. 1(3), 209–215 (1979)
Khuller, S., Sussmann, Y.J.: The capacitated \(k\)-center problem. SIAM J. Discrete Math. 13(3), 403–418 (2000)
Khuller, S., Pless, R., Sussmann, Y.J.: Fault tolerant \(k\)-center problems. Theor. Comput. Sci. 242(1–2), 237–245 (2000)
Krumke, S.: On a generalization of the \(p\)-center problem. Inf. Process. Lett. 56(2), 67–71 (1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fernandes, C.G., de Paula, S.P., Pedrosa, L.L.C. (2016). Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. In: Kranakis, E., Navarro, G., Chávez, E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science(), vol 9644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49529-2_33
Download citation
DOI: https://doi.org/10.1007/978-3-662-49529-2_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49528-5
Online ISBN: 978-3-662-49529-2
eBook Packages: Computer ScienceComputer Science (R0)