Abstract
Real networks have in common that they evolve over time and their dynamics have a huge impact on their structure. Clustering is an efficient tool to reduce the complexity to allow representation of the data. In 2014, Eisenstat et al. introduced a dynamic version of this classic problem where the distances evolve with time and where coherence over time is enforced by introducing a cost for clients to change their assigned facility. They designed a \(\varTheta (\ln n)\)-approximation. An O(1)-approximation for the metric case was proposed later on by An et al. (2015). Both articles aimed at minimizing the sum of all client-facility distances; however, other metrics may be more relevant. In this article we aim to minimize the sum of the radii of the clusters instead. We obtain an asymptotically optimal \(\varTheta (\ln n)\)-approximation algorithm where n is the number of clients and show that existing algorithms from An et al. (2015) do not achieve a constant approximation in the metric variant of this setting.
This work was supported by Grants ANR-12-BS02-005 RDAM and IXXI-Molecal.
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
Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)
Stehlé, J., Voirin, N., Barrat, A., Cattuto, C., Isella, L., Pinton, J., Quaggiotto, M., den Broeck, W.V., Régis, C., Lina, B., Vanhems, P.: High-resolution measurements of face-to-face contact patterns in a primary school. PLoS ONE 6(8), e23176 (2011)
Sundaresan, S.R., Fischhoff, I.R., Dushoff, J., Rubenstein, D.I.: Network metrics reveal differences in social organization between two fission-fusion species, grevy’s zebra and onager. Oecologia 151(1), 140–149 (2007)
Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86, 3200–3203 (2001)
Tantipathananandh, C., Berger-Wolf, T.Y., Kempe, D.: A framework for community identification in dynamic social networks. In: SIGKDD, pp. 717–726 (2007)
Fotakis, D., Koutris, P.: Online sum-radii clustering. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 395–406. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32589-2_36
Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45–58 (2013)
Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2), 417–441 (2004)
Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31(1), 228–248 (1999)
Eisenstat, D., Mathieu, C., Schabanel, N.: Facility location in evolving metrics. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 459–470. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43951-7_39
An, H., Norouzi-Fard, A., Svensson, O.: Dynamic facility location via exponential clocks. In: SODA, pp. 708–721 (2015)
Fernandes, C.G., Oshiro, M.T., Schabanel, N.: Dynamic clustering of evolving networks: some results on the line. In: AlgoTel, pp. 1–4, May 2013
Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411–432 (2006)
Behsaz, B., Salavatipour, M.R.: On minimum sum of radii and diameters clustering. Algorithmica 73(1), 143–165 (2015)
Hochbaum, D.S.: Heuristics for the fixed cost median problem. Math. Program. 22(1), 148–162 (1982)
Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC, pp. 624–633 (2014)
Lee, Y.T., Sidford, A.: Path finding methods for linear programming: solving linear programs in Õ(vrank) iterations and faster algorithms for maximum flow. In: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 424–433. IEEE Computer Society, Washington (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Blanchard, N.K., Schabanel, N. (2017). Dynamic Sum-Radii Clustering. In: Poon, SH., Rahman, M., Yen, HC. (eds) WALCOM: Algorithms and Computation. WALCOM 2017. Lecture Notes in Computer Science(), vol 10167. Springer, Cham. https://doi.org/10.1007/978-3-319-53925-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-53925-6_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53924-9
Online ISBN: 978-3-319-53925-6
eBook Packages: Computer ScienceComputer Science (R0)