{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T13:06:33Z","timestamp":1748264793712,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T00:00:00Z","timestamp":1701302400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T00:00:00Z","timestamp":1701302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["416767905","390685813"],"award-info":[{"award-number":["416767905","390685813"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008131","name":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008131","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In a hierarchical clustering problem the task is to compute a series of mutually compatible clusterings of a finite metric space <jats:inline-formula><jats:alternatives><jats:tex-math>$$(P,{{\\,\\textrm{dist}\\,}})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>P<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mtext>dist<\/mml:mtext>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Starting with the clustering where every point forms its own cluster, one iteratively merges two clusters until only one cluster remains. Complete linkage is a well-known and popular algorithm to compute such clusterings: in every step it merges the two clusters whose union has the smallest radius (or diameter) among all currently possible merges. We prove that the radius (or diameter) of every <jats:italic>k<\/jats:italic>-clustering computed by complete linkage is at most by factor <jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>) (or <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(k^{\\ln (3)\/\\ln (2)})=O(k^{1{.}59})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mo>ln<\/mml:mo>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mn>3<\/mml:mn>\n                          <mml:mo>)<\/mml:mo>\n                          <mml:mo>\/<\/mml:mo>\n                          <mml:mo>ln<\/mml:mo>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mn>1.59<\/mml:mn>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) worse than an optimal <jats:italic>k<\/jats:italic>-clustering minimizing the radius (or diameter). Furthermore we give a negative answer to the question proposed by Dasgupta and Long (J Comput Syst Sci 70(4):555\u2013569, 2005. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1016\/j.jcss.2004.10.006\">https:\/\/doi.org\/10.1016\/j.jcss.2004.10.006<\/jats:ext-link>), who show a lower bound of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega (\\log (k))$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and ask if the approximation guarantee is in fact <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Theta (\\log (k))$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We present instances where complete linkage performs poorly in the sense that the <jats:italic>k<\/jats:italic>-clustering computed by complete linkage is off by a factor of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega (k)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> from an optimal solution for radius and diameter. We conclude that in general metric spaces complete linkage does not perform asymptotically better than single linkage, merging the two clusters with smallest inter-cluster distance, for which we prove an approximation guarantee of <jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>).<\/jats:p>","DOI":"10.1007\/s10994-023-06486-8","type":"journal-article","created":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T18:01:44Z","timestamp":1701367304000},"page":"489-518","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Upper and lower bounds for complete linkage in general metric spaces"],"prefix":"10.1007","volume":"113","author":[{"given":"Anna","family":"Arutyunova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Gro\u00dfwendt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Melanie","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Wargalla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,30]]},"reference":[{"issue":"1","key":"6486_CR1","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. (2014). Analysis of agglomerative clustering. Algorithmica, 69(1), 184\u2013215. https:\/\/doi.org\/10.1007\/s00453-012-9717-4","journal-title":"Algorithmica"},{"key":"6486_CR2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1171321","author":"S Ahmadian","year":"2020","unstructured":"Ahmadian, S., Norouzi-Fard, A., Svensson, O., & Ward, J. (2020). Better guarantees for k-means and Euclidean k-median by primal\u2013dual algorithms. SIAM Journal on Computing. https:\/\/doi.org\/10.1137\/18M1171321","journal-title":"SIAM Journal on Computing"},{"key":"6486_CR3","doi-asserted-by":"publisher","unstructured":"Arutyunova, A., & R\u00f6glin, H. (2022). The price of hierarchical clustering. In 30th Annual European symposium on algorithms, ESA 2022 (Vol. 244, pp. 10:1\u201310:14). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2022.10.","DOI":"10.4230\/LIPIcs.ESA.2022.10"},{"key":"6486_CR4","doi-asserted-by":"publisher","unstructured":"Arutyunova, A., Gro\u00dfwendt, A., R\u00f6glin, H., Schmidt, M., & Wargalla, J. (2021). Upper and lower bounds for complete linkage in general metric spaces. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX\/RANDOM 2021 (Vol. 207, pp. 18:1\u201318:22). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2021.18.","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.18"},{"key":"6486_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-022-00851-4","author":"F Bock","year":"2022","unstructured":"Bock, F. (2022). Hierarchy cost of hierarchical clusterings. Journal of Combinatorial Optimization. https:\/\/doi.org\/10.1007\/s10878-022-00851-4","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2","key":"6486_CR6","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2981561","volume":"13","author":"J Byrka","year":"2017","unstructured":"Byrka, J., Pensyl, T. W., Rybicki, B., Srinivasan, A., & Trinh, K. (2017). An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms, 13(2), 23:1-23:31. https:\/\/doi.org\/10.1145\/2981561","journal-title":"ACM Transactions on Algorithms"},{"issue":"6","key":"6486_CR7","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. (2004). Incremental clustering and dynamic information retrieval. SIAM Journal on Computing, 33(6), 1417\u20131440. https:\/\/doi.org\/10.1137\/S0097539702418498","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"6486_CR8","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. (2005). Performance guarantees for hierarchical clustering. Journal of Computer and System Sciences, 70(4), 555\u2013569. https:\/\/doi.org\/10.1016\/j.jcss.2004.10.006","journal-title":"Journal of Computer and System Sciences"},{"key":"6486_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. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38, 293\u2013306. https:\/\/doi.org\/10.1016\/0304-3975(85)90224-5","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"6486_CR10","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. (2017). Improved analysis of complete-linkage clustering. Algorithmica, 78(4), 1131\u20131150. https:\/\/doi.org\/10.1007\/s00453-017-0284-6","journal-title":"Algorithmica"},{"key":"6486_CR11","doi-asserted-by":"publisher","unstructured":"Gro\u00dfwendt, A., R\u00f6glin, H., & Schmidt, M. (2019). Analysis of ward\u2019s method. In Chan, T. M. (Ed.), Proceedings of the Thirtieth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 2939\u20132957). SIAM. https:\/\/doi.org\/10.1137\/1.9781611975482.182.","DOI":"10.1137\/1.9781611975482.182"},{"key":"6486_CR12","unstructured":"Gro\u00dfwendt, A. K. (2020). Theoretical analysis of hierarchical clustering and the shadow vertex algorithm. Ph.D. thesis, University of Bonn. http:\/\/hdl.handle.net\/20.500.11811\/8348"},{"key":"6486_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.105941","volume":"158","author":"DE Hershkowitz","year":"2020","unstructured":"Hershkowitz, D. E., & Kehne, G. (2020). Reverse greedy is bad for k-center. Information Processing Letters, 158, 105941. https:\/\/doi.org\/10.1016\/j.ipl.2020.105941","journal-title":"Information Processing Letters"},{"issue":"3","key":"6486_CR14","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF01874389","volume":"1","author":"DS Hochbaum","year":"1984","unstructured":"Hochbaum, D. S. (1984). When are np-hard location problems easy? Annals of Operations Research, 1(3), 201\u2013214. https:\/\/doi.org\/10.1007\/BF01874389","journal-title":"Annals of Operations Research"},{"issue":"2","key":"6486_CR15","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D. S., & Shmoys, D. B. (1985). A best possible heuristic for the k-center problem. Mathematical Operations Research, 10(2), 180\u2013184. https:\/\/doi.org\/10.1287\/moor.10.2.180","journal-title":"Mathematical Operations Research"},{"issue":"3","key":"6486_CR16","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W Hsu","year":"1979","unstructured":"Hsu, W., & Nemhauser, G. L. (1979). Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3), 209\u2013215. https:\/\/doi.org\/10.1016\/0166-218X(79)90044-1","journal-title":"Discrete Applied Mathematics"},{"issue":"8","key":"6486_CR17","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. (2010). A general approach for incremental approximation and hierarchical clustering. SIAM Journal on Computing, 39(8), 3633\u20133669. https:\/\/doi.org\/10.1137\/070698257","journal-title":"SIAM Journal on Computing"},{"key":"6486_CR18","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. (1963). Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58, 236\u2013244. https:\/\/doi.org\/10.1080\/01621459.1963.10500845","journal-title":"Journal of the American Statistical Association"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06486-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-023-06486-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06486-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T21:42:48Z","timestamp":1703194968000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-023-06486-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,30]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["6486"],"URL":"https:\/\/doi.org\/10.1007\/s10994-023-06486-8","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2023,11,30]]},"assertion":[{"value":"20 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2023","order":4,"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":"Consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}