{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T20:49:49Z","timestamp":1784839789743,"version":"3.55.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T00:00:00Z","timestamp":1751414400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T00:00:00Z","timestamp":1751414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003484","name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003484","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Hierarchical Clustering is a popular tool for understanding the hereditary properties of a data set. Such a clustering is actually a sequence of clusterings that starts with the trivial clustering in which every data point forms its own cluster and then successively merges two existing clusters until all points are in the same cluster. A hierarchical clustering achieves an approximation factor of\u00a0<jats:inline-formula>\n              <jats:tex-math>$$\\alpha $$<\/jats:tex-math>\n            <\/jats:inline-formula> if the costs of each <jats:italic>k<\/jats:italic>-clustering in the hierarchy are at most <jats:inline-formula>\n              <jats:tex-math>$$\\alpha $$<\/jats:tex-math>\n            <\/jats:inline-formula> times the costs of an optimal <jats:italic>k<\/jats:italic>-clustering. We study as cost functions the maximum (discrete) radius of any cluster (<jats:italic>k<\/jats:italic>-center problem) and the maximum diameter of any cluster (<jats:italic>k<\/jats:italic>-diameter problem). In general, the optimal clusterings do not form a hierarchy and hence an approximation factor of\u00a01 cannot be achieved. We call the smallest approximation factor that can be achieved for any instance the <jats:italic>price of hierarchy<\/jats:italic>. For the <jats:italic>k<\/jats:italic>-diameter problem we improve the upper bound on the price of hierarchy to <jats:inline-formula>\n              <jats:tex-math>$$3+2\\sqrt{2}\\approx 5.83$$<\/jats:tex-math>\n            <\/jats:inline-formula>. Moreover we significantly improve the lower bounds for <jats:italic>k<\/jats:italic>-center and <jats:italic>k<\/jats:italic>-diameter, proving a price of hierarchy of exactly 4 and <jats:inline-formula>\n              <jats:tex-math>$$3+2\\sqrt{2}$$<\/jats:tex-math>\n            <\/jats:inline-formula>, respectively.<\/jats:p>","DOI":"10.1007\/s00453-025-01327-7","type":"journal-article","created":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T06:10:06Z","timestamp":1751436606000},"page":"1420-1452","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Price of Hierarchical Clustering"],"prefix":"10.1007","volume":"87","author":[{"given":"Anna","family":"Arutyunova","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,7,2]]},"reference":[{"key":"1327_CR1","doi-asserted-by":"publisher","unstructured":"Arutyunova, A., R\u00f6glin, H.: The price of hierarchical clustering. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms, ESA 2022, September 5\u20139, 2022, Berlin\/Potsdam, Germany. LIPIcs, vol. 244, pp. 10\u201311014. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Berlin\/Potsdam, Germany (2022). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2022.10","DOI":"10.4230\/LIPICS.ESA.2022.10"},{"issue":"4","key":"1327_CR2","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/j.jcss.2004.10.006","volume":"70","author":"S Dasgupta","year":"2005","unstructured":"Dasgupta, S., Long, P.M.: Performance guarantees for hierarchical clustering. J. Comput. Syst. Sci. 70(4), 555\u2013569 (2005). https:\/\/doi.org\/10.1016\/j.jcss.2004.10.006","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"1327_CR3","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1137\/S0097539702418498","volume":"33","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. SIAM J. Comput. 33(6), 1417\u20131440 (2004). https:\/\/doi.org\/10.1137\/S0097539702418498","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1327_CR4","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/j.jcss.2005.09.004","volume":"72","author":"CG Plaxton","year":"2006","unstructured":"Plaxton, C.G.: Approximation algorithms for hierarchical location problems. J. Comput. Syst. Sci. 72(3), 425\u2013443 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2005.09.004","journal-title":"J. Comput. Syst. Sci."},{"issue":"8","key":"1327_CR5","doi-asserted-by":"publisher","first-page":"3633","DOI":"10.1137\/070698257","volume":"39","author":"G Lin","year":"2010","unstructured":"Lin, G., Nagarajan, C., Rajaraman, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. SIAM J. Comput. 39(8), 3633\u20133669 (2010). https:\/\/doi.org\/10.1137\/070698257","journal-title":"SIAM J. Comput."},{"key":"1327_CR6","unstructured":"Gro\u00dfwendt, A.-K.: Theoretical analysis of hierarchical clustering and the shadow vertex algorithm. Ph.D. thesis, University of Bonn (2020). http:\/\/hdl.handle.net\/20.500.11811\/8348"},{"issue":"3","key":"1327_CR7","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/s00224-009-9186-6","volume":"45","author":"A Das","year":"2009","unstructured":"Das, A., Kenyon-Mathieu, C.: On hierarchical diameter-clustering and the supplier problem. Theory Comput. Syst. 45(3), 497\u2013511 (2009). https:\/\/doi.org\/10.1007\/s00224-009-9186-6","journal-title":"Theory Comput. Syst."},{"key":"1327_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-022-00851-4","author":"F Bock","year":"2022","unstructured":"Bock, F.: Hierarchy cost of hierarchical clusterings. J. Comb. Optim. (2022). https:\/\/doi.org\/10.1007\/s10878-022-00851-4","journal-title":"J. Comb. Optim."},{"key":"1327_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 38, 293\u2013306 (1985). https:\/\/doi.org\/10.1016\/0304-3975(85)90224-5","journal-title":"Theoret. Comput. Sci."},{"key":"1327_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.patrec.2018.01.015","volume":"104","author":"SA Mondal","year":"2018","unstructured":"Mondal, S.A.: An improved approximation algorithm for hierarchical clustering. Pattern Recognit. Lett. 104, 23\u201328 (2018). https:\/\/doi.org\/10.1016\/j.patrec.2018.01.015","journal-title":"Pattern Recognit. Lett."},{"key":"1327_CR11","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Grandoni, F., Lee, E., Schwiegelshohn, C.: Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22\u201325, 2023, pp. 940\u2013986. SIAM, Florence, Italy (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch37","DOI":"10.1137\/1.9781611977554.ch37"},{"key":"1327_CR12","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Esfandiari, H., Mirrokni, V.S., Narayanan, S.: Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets. In: STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20\u201324, 2022, pp. 1621\u20131628. ACM, Rome, Italy (2022). https:\/\/doi.org\/10.1145\/3519935.3520011","DOI":"10.1145\/3519935.3520011"},{"issue":"3","key":"1327_CR13","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3), 533\u2013550 (1986). https:\/\/doi.org\/10.1145\/5925.5933","journal-title":"J. ACM"},{"issue":"301","key":"1327_CR14","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1080\/01621459.1963.10500845","volume":"58","author":"JH Ward Jr","year":"1963","unstructured":"Ward, J.H., Jr.: Hierarchical grouping to optimize an objective function. J. Am. Stat. Assoc. 58(301), 236\u2013244 (1963). https:\/\/doi.org\/10.1080\/01621459.1963.10500845","journal-title":"J. Am. Stat. Assoc."},{"issue":"1","key":"1327_CR15","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/s00453-012-9717-4","volume":"69","author":"MR Ackermann","year":"2014","unstructured":"Ackermann, M.R., Bl\u00f6mer, J., Kuntze, D., Sohler, C.: Analysis of agglomerative clustering. Algorithmica 69(1), 184\u2013215 (2014). https:\/\/doi.org\/10.1007\/s00453-012-9717-4","journal-title":"Algorithmica"},{"issue":"4","key":"1327_CR16","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1007\/s00453-017-0284-6","volume":"78","author":"A Gro\u00dfwendt","year":"2017","unstructured":"Gro\u00dfwendt, A., R\u00f6glin, H.: Improved analysis of complete-linkage clustering. Algorithmica 78(4), 1131\u20131150 (2017). https:\/\/doi.org\/10.1007\/s00453-017-0284-6","journal-title":"Algorithmica"},{"key":"1327_CR17","doi-asserted-by":"publisher","unstructured":"Arutyunova, A., Gro\u00dfwendt, A., R\u00f6glin, H., Schmidt, M., Wargalla, J.: Upper and lower bounds for complete linkage in general metric spaces. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM), pp. 18\u201311822 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2021.18","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.18"},{"key":"1327_CR18","doi-asserted-by":"publisher","unstructured":"Gro\u00dfwendt, A., R\u00f6glin, H., Schmidt, M.: Analysis of ward\u2019s method. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2939\u20132957 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.182","DOI":"10.1137\/1.9781611975482.182"},{"key":"1327_CR19","doi-asserted-by":"publisher","unstructured":"Dasgupta, S.: A cost function for similarity-based hierarchical clustering. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pp. 118\u2013127 (2016). https:\/\/doi.org\/10.1145\/2897518.2897527","DOI":"10.1145\/2897518.2897527"},{"key":"1327_CR20","doi-asserted-by":"publisher","unstructured":"Charikar, M., Chatziafratis, V.: Approximate hierarchical clustering via sparsest cut and spreading metrics. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841\u2013854 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.53","DOI":"10.1137\/1.9781611974782.53"},{"key":"1327_CR21","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Kanade, V., Mallmann-Trenn, F., Mathieu, C.: Hierarchical clustering: objective functions and algorithms. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 378\u2013397 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.26","DOI":"10.1137\/1.9781611975031.26"},{"key":"1327_CR22","doi-asserted-by":"publisher","unstructured":"Wang, Y., Moseley, B.: An objective for hierarchical clustering in Euclidean space and its connection to bisecting k-means. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, pp. 6307\u20136314 (2020). https:\/\/doi.org\/10.1609\/aaai.v34i04.6099","DOI":"10.1609\/aaai.v34i04.6099"},{"issue":"3","key":"1327_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-014-5065-0","volume":"57","author":"W Dai","year":"2014","unstructured":"Dai, W.: A 16-competitive algorithm for hierarchical median problem. Sci. China Inf. Sci. 57(3), 1\u20137 (2014). https:\/\/doi.org\/10.1007\/s11432-014-5065-0","journal-title":"Sci. China Inf. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01327-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01327-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01327-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T23:02:31Z","timestamp":1757026951000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01327-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,2]]},"references-count":23,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["1327"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01327-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,2]]},"assertion":[{"value":"23 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}