{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T06:37:03Z","timestamp":1773729423786,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T00:00:00Z","timestamp":1590710400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T00:00:00Z","timestamp":1590710400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["340506"],"award-info":[{"award-number":["340506"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s00453-020-00721-7","type":"journal-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T04:08:02Z","timestamp":1590725282000},"page":"3183-3194","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Dynamic Clustering to Minimize the Sum of Radii"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5008-6530","authenticated-orcid":false,"given":"Monika","family":"Henzinger","sequence":"first","affiliation":[]},{"given":"Dariusz","family":"Leniowski","sequence":"additional","affiliation":[]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,29]]},"reference":[{"key":"721_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Addanki, R., Grandoni, F., Panigrahi, D., Saha, B.: Dynamic set cover: improved algorithms and lower bounds. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23\u201326, 2019, pp. 114\u2013125. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316376","DOI":"10.1145\/3313276.3316376"},{"key":"721_CR2","doi-asserted-by":"crossref","unstructured":"Alt, H., Arkin, E.M., Br\u00f6nnimann, H., Erickson, J., Fekete, S.P., Knauer, C., Lenchner, J., Mitchell, J.S.B., Whittlesey, K.: Minimum-cost coverage of point sets by disks. In: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, SCG \u201906, pp. 449\u2013458. ACM, New York (2006)","DOI":"10.1145\/1137856.1137922"},{"key":"721_CR3","unstructured":"Bandyapadhyay, S., Varadarajan, K.R.: Approximate clustering via metric partitioning. CoRR arXiv:1507.02222 (2015)"},{"issue":"1","key":"721_CR4","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/130914140","volume":"44","author":"S Baswana","year":"2015","unstructured":"Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in o(log n) update time. SIAM J. Comput. 44(1), 88\u2013113 (2015). https:\/\/doi.org\/10.1137\/130914140","journal-title":"SIAM J. Comput."},{"issue":"1","key":"721_CR5","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00453-014-9907-3","volume":"73","author":"B Behsaz","year":"2015","unstructured":"Behsaz, B., Salavatipour, M.R.: On minimum sum of radii and diameters clustering. Algorithmica 73(1), 143\u2013165 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9907-3","journal-title":"Algorithmica"},{"key":"721_CR6","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: Cohen, W.W., Moore, A. (eds.) Machine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25\u201329, 2006, ACM International Conference Proceeding Series, vol. 148, pp. 97\u2013104. ACM (2006). https:\/\/doi.org\/10.1145\/1143844.1143857","DOI":"10.1145\/1143844.1143857"},{"key":"721_CR7","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Design of dynamic algorithms via primal\u2013dual method. In: Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, pp. 206\u2013218 (2015)","DOI":"10.1007\/978-3-662-47672-7_17"},{"key":"721_CR8","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015, pp. 785\u2013804 (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.54","DOI":"10.1137\/1.9781611973730.54"},{"key":"721_CR9","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D.: New deterministic approximation algorithms for fully dynamic matching. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18\u201321, 2016, pp. 398\u2013411 (2016). https:\/\/doi.org\/10.1145\/2897518.2897568","DOI":"10.1145\/2897518.2897568"},{"key":"721_CR10","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D.: Fully dynamic approximate maximum matching and minimum vertex cover in $$O(\\log ^3 n)$$ worst case update time. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319, pp. 470\u2013489 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.30","DOI":"10.1137\/1.9781611974782.30"},{"key":"721_CR11","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D.: A new deterministic algorithm for dynamic set cover. In: Zuckerman, D. (ed.) 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9\u201312, 2019, pp. 406\u2013423. IEEE Computer Society (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00033","DOI":"10.1109\/FOCS.2019.00033"},{"key":"721_CR12","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D., Wu, X.: An improved algorithm for dynamic set cover. CoRR arXiv:2002.11171 (2020)","DOI":"10.1109\/FOCS.2019.00033"},{"issue":"2\u20133","key":"721_CR13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal: dual approach. Found. Trends Theor. Comput. Sci. 3(2\u20133), 93\u2013263 (2009). https:\/\/doi.org\/10.1561\/0400000024","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"2","key":"721_CR14","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1145\/130226.134466","volume":"11","author":"F Can","year":"1993","unstructured":"Can, F.: Incremental clustering for dynamic information processing. ACM Trans. Inf. Syst. 11(2), 143\u2013164 (1993). https:\/\/doi.org\/10.1145\/130226.134466","journal-title":"ACM Trans. Inf. Syst."},{"issue":"2","key":"721_CR15","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.jcss.2003.07.014","volume":"68","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2), 417\u2013441 (2004). https:\/\/doi.org\/10.1016\/j.jcss.2003.07.014","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"721_CR16","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s00453-011-9586-2","volume":"65","author":"J Csirik","year":"2013","unstructured":"Csirik, J., Epstein, L., Imreh, C., Levin, A.: Online clustering with variable sized clusters. Algorithmica 65(2), 251\u2013274 (2013). https:\/\/doi.org\/10.1007\/s00453-011-9586-2","journal-title":"Algorithmica"},{"issue":"3","key":"721_CR17","first-page":"185","volume":"7","author":"SR Doddi","year":"2000","unstructured":"Doddi, S.R., Marathe, M.V., Ravi, S.S., Taylor, D.S., Widmayer, P.: Approximation algorithms for clustering to minimize the sum of diameters. Nord. J. Comput. 7(3), 185\u2013203 (2000)","journal-title":"Nord. J. Comput."},{"key":"721_CR18","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Koutris, P.: Online sum-radii clustering. CoRR arXiv:1109.5325 (2011)","DOI":"10.1007\/978-3-642-32589-2_36"},{"key":"721_CR19","unstructured":"Gibson, M., Kanade, G., Krohn, E., Pirwani, I.A., Varadarajan, K.: On clustering to minimize the sum of radii. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201908, pp. 819\u2013825. Society for Industrial and Applied Mathematics, Philadelphia (2008). http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347172"},{"key":"721_CR20","doi-asserted-by":"crossref","unstructured":"Gibson, M., Kanade, G., Krohn, E., Pirwani, I.A., Varadarajan, K.: On metric clustering to minimize the sum of radii. In: Proceedings of the 11th Scandinavian Workshop on Algorithm Theory, SWAT \u201908, pp. 282\u2013293. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-69903-3_26"},{"key":"721_CR21","unstructured":"Goranci, G., Henzinger, M., Leniowski, D.: A Tree structure for dynamic facility location. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms (ESA 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 112, pp. 39:1\u201339:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.39. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9502"},{"key":"721_CR22","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Kumar, A., Panigrahi, D.: Online and dynamic algorithms for set cover. CoRR arXiv:1611.05646 (2016)","DOI":"10.1145\/3055399.3055493"},{"issue":"2","key":"721_CR23","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01896987","volume":"4","author":"P Hansen","year":"1987","unstructured":"Hansen, P., Jaumard, B.: Minimum sum of diameters clustering. J. Classif. 4(2), 215\u2013226 (1987)","journal-title":"J. Classif."},{"issue":"1\u20133","key":"721_CR24","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF02614317","volume":"79","author":"P Hansen","year":"1997","unstructured":"Hansen, P., Jaumard, B.: Cluster analysis and mathematical programming. Math. Program. 79(1\u20133), 191\u2013215 (1997). https:\/\/doi.org\/10.1007\/BF02614317","journal-title":"Math. Program."},{"key":"721_CR25","unstructured":"Henzinger, M., Leniowski, D., Mathieu, C.: Dynamic clustering to minimize the sum of radii. In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4\u20136, 2017, Vienna, Austria, pp. 48:1\u201348:10 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.48"},{"key":"721_CR26","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201904, pp. 798\u2013807. Society for Industrial and Applied Mathematics, Philadelphia (2004). http:\/\/dl.acm.org\/citation.cfm?id=982792.982913"},{"issue":"4","key":"721_CR27","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1016\/j.comnet.2004.08.012","volume":"47","author":"N Lev-Tov","year":"2005","unstructured":"Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Netw. ISDN Syst. 47(4), 489\u2013501 (2005). https:\/\/doi.org\/10.1016\/j.comnet.2004.08.012","journal-title":"Comput. Netw. ISDN Syst."},{"key":"721_CR28","doi-asserted-by":"crossref","unstructured":"Proietti, G., Widmayer, P.: Partitioning the nodes of a graph to minimize the sum of subgraph radii. In: Proceedings of the 17th International Conference on Algorithms and Computation, ISAAC\u201906, pp. 578\u2013587. Springer, Berlin (2006)","DOI":"10.1007\/11940128_58"},{"issue":"1","key":"721_CR29","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"SE Schaeffer","year":"2007","unstructured":"Schaeffer, S.E.: Survey: graph clustering. Comput. Sci. Rev. 1(1), 27\u201364 (2007). https:\/\/doi.org\/10.1016\/j.cosrev.2007.05.001","journal-title":"Comput. Sci. Rev."},{"key":"721_CR30","doi-asserted-by":"crossref","unstructured":"Solomon, S.: Fully dynamic maximal matching in constant update time. In: IEEE FOCS (2016). arXiv:1604.08491","DOI":"10.1109\/FOCS.2016.43"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00721-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00721-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00721-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T23:59:18Z","timestamp":1622246358000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00721-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,29]]},"references-count":30,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["721"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00721-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,29]]},"assertion":[{"value":"11 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}