Dynamic sum-radii clustering. (English) Zbl 1485.90061
Poon, Sheung-Hung (ed.) et al., WALCOM: algorithms and computation. 11th international conference and workshops, WALCOM 2017, Hsinchu, Taiwan, March 29–31, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10167, 30-41 (2017).
Summary: 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 [Lect. Notes Comput. Sci. 8573, 459–470 (2014; Zbl 1410.90116)], D. 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 H.-C. An et al. [in: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 708–721 (2015; Zbl 1371.90071)]. 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., loc. cit.] do not achieve a constant approximation in the metric variant of this setting.
For the entire collection see [Zbl 1358.68017].
For the entire collection see [Zbl 1358.68017].
MSC:
| 90B80 | Discrete location and assignment |
| 68W25 | Approximation algorithms |
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003) · Zbl 1029.68010 · doi:10.1137/S003614450342480 |
| [2] | 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) · doi:10.1371/journal.pone.0023176 |
| [3] | 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) · doi:10.1007/s00442-006-0553-6 |
| [4] | Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86, 3200–3203 (2001) · doi:10.1103/PhysRevLett.86.3200 |
| [5] | Tantipathananandh, C., Berger-Wolf, T.Y., Kempe, D.: A framework for community identification in dynamic social networks. In: SIGKDD, pp. 717–726 (2007) · doi:10.1145/1281192.1281269 |
| [6] | 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 · Zbl 1365.68476 · doi:10.1007/978-3-642-32589-2_36 |
| [7] | Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45–58 (2013) · Zbl 1281.68236 · doi:10.1016/j.ic.2012.01.007 |
| [8] | Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2), 417–441 (2004) · Zbl 1091.68099 · doi:10.1016/j.jcss.2003.07.014 |
| [9] | Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31(1), 228–248 (1999) · Zbl 0928.68137 · doi:10.1006/jagm.1998.0993 |
| [10] | 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 · Zbl 1410.90116 · doi:10.1007/978-3-662-43951-7_39 |
| [11] | An, H., Norouzi-Fard, A., Svensson, O.: Dynamic facility location via exponential clocks. In: SODA, pp. 708–721 (2015) · Zbl 1371.90071 · doi:10.1137/1.9781611973730.48 |
| [12] | 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 |
| [13] | Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411–432 (2006) · Zbl 1151.90590 · doi:10.1137/S0097539703435716 |
| [14] | Behsaz, B., Salavatipour, M.R.: On minimum sum of radii and diameters clustering. Algorithmica 73(1), 143–165 (2015) · Zbl 1319.68251 · doi:10.1007/s00453-014-9907-3 |
| [15] | Hochbaum, D.S.: Heuristics for the fixed cost median problem. Math. Program. 22(1), 148–162 (1982) · Zbl 0473.90029 · doi:10.1007/BF01581035 |
| [16] | Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC, pp. 624–633 (2014) · Zbl 1315.91001 · doi:10.1145/2591796.2591884 |
| [17] | 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) · doi:10.1109/FOCS.2014.52 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
