{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:25Z","timestamp":1750309165613,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T00:00:00Z","timestamp":1712707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"VILLUM","award":["16582"],"award-info":[{"award-number":["16582"]}]},{"DOI":"10.13039\/501100020975","name":"Basic Algorithms Research Copenhagen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100020975","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union\u2019s Horizon 2020","award":["801199"],"award-info":[{"award-number":["801199"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            We consider the numerical taxonomy problem of fitting a positive distance function\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({\\mathcal {D}:{S\\choose 2}\\rightarrow \\mathbb {R}_{\\gt 0}}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            by a tree metric. We want a tree\n            <jats:italic>T<\/jats:italic>\n            with positive edge weights and including\n            <jats:italic>S<\/jats:italic>\n            among the vertices so that their distances in\n            <jats:italic>T<\/jats:italic>\n            match those in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {D}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . A nice application is in evolutionary biology where the tree\n            <jats:italic>T<\/jats:italic>\n            aims to approximate thebranching process leading to the observed distances in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {D}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            [Cavalli-Sforza and Edwards 1967]. We consider the total error, that is, the sum of distance errors over all pairs of points. We present a deterministic polynomial time algorithm minimizing the total error within a constant factor. We can do this both for general trees and for the special case of ultrametrics with a root having the same distance to all vertices in\n            <jats:italic>S<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            The problems are APX-hard, so a constant factor is the best we can hope for in polynomial time. The best previous approximation factor was\n            <jats:italic>O<\/jats:italic>\n            ((log\n            <jats:italic>n<\/jats:italic>\n            )(log log\n            <jats:italic>n<\/jats:italic>\n            )) by Ailon and Charikar [2005], who wrote \u201cdetermining whether an\n            <jats:italic>O<\/jats:italic>\n            (1) approximation can be obtained is a fascinating question.\u201d\n          <\/jats:p>","DOI":"10.1145\/3639453","type":"journal-article","created":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T21:58:12Z","timestamp":1704232692000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0779-8962","authenticated-orcid":false,"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google Research, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2232-4279","authenticated-orcid":false,"given":"Debarati","family":"Das","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5830-5830","authenticated-orcid":false,"given":"Evangelos","family":"Kipouridis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3888-7391","authenticated-orcid":false,"given":"Nikos","family":"Parotsidis","sequence":"additional","affiliation":[{"name":"Google Research, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5237-1709","authenticated-orcid":false,"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,10]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"11576","volume-title":"NeurIPS","author":"Abboud Amir","year":"2019","unstructured":"Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge. 2019. Subquadratic high-dimensional hierarchical clustering. In NeurIPS. 11576\u201311586."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795296334"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/100806886"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_3_2_6_2","first-page":"153","volume-title":"COLT","author":"Alon Noga","year":"2020","unstructured":"Noga Alon, Yossi Azar, and Danny Vainstein. 2020. Hierarchical clustering: A 0.585 revenue approximation. In COLT, Vol. 125. 153\u2013162."},{"key":"e_1_3_2_7_2","first-page":"671","volume-title":"STOC","author":"Balcan Maria-Florina","year":"2008","unstructured":"Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. 2008. A discriminative framework for clustering via similarity functions. In STOC. 671\u2013680."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_3_2_9_2","first-page":"184","volume-title":"FOCS","author":"Bartal Yair","year":"1996","unstructured":"Yair Bartal. 1996. Probabilistic approximations of metric spaces and its algorithmic applications. In FOCS. 184\u2013193."},{"key":"e_1_3_2_10_2","first-page":"737","volume-title":"SODA","author":"Byrka Jaros\u0142aw","year":"2014","unstructured":"Jaros\u0142aw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. 2014. An improved approximation for k-median, and positive correlation in budgeted optimization. In SODA. 737\u2013756."},{"key":"e_1_3_2_11_2","first-page":"1425","article-title":"Characterization, stability and convergence of hierarchical clustering methods.","volume":"11","author":"Carlsson Gunnar E.","year":"2010","unstructured":"Gunnar E. Carlsson and Facundo M\u00e9moli. 2010. Characterization, stability and convergence of hierarchical clustering methods. J. Mach. Learn. Res. 11, 47 (Apr.2010), 1425\u20131470.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_12_2","first-page":"233","article-title":"Phylogenetic analysis models and estimation procedures","volume":"19","author":"Cavalli-Sforza L. L.","year":"1967","unstructured":"L. L. Cavalli-Sforza and A. W. F. Edwards. 1967. Phylogenetic analysis models and estimation procedures. Am. J. Hum. Genet. 19, 3 (1967), 233\u2013257.","journal-title":"Am. J. Hum. Genet."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(78)90089-5"},{"key":"e_1_3_2_14_2","volume-title":"NeurIPS","author":"Chami Ines","year":"2020","unstructured":"Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher R\u00e9. 2020. From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering. In NeurIPS."},{"key":"e_1_3_2_15_2","first-page":"841","volume-title":"SODA","author":"Charikar Moses","year":"2017","unstructured":"Moses Charikar and Vaggos Chatziafratis. 2017. Approximate hierarchical clustering via sparsest cut and spreading metrics. In SODA. 841\u2013854."},{"key":"e_1_3_2_16_2","first-page":"2291","volume-title":"SODA","author":"Charikar Moses","year":"2019","unstructured":"Moses Charikar, Vaggos Chatziafratis, and Rad Niazadeh. 2019. Hierarchical clustering better than average-linkage. In SODA. 2291\u20132304."},{"key":"e_1_3_2_17_2","first-page":"2721","volume-title":"AISTATS","author":"Charikar Moses","year":"2019","unstructured":"Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, and Grigory Yaroslavtsev. 2019. Hierarchical clustering for euclidean data. In AISTATS. 2721\u20132730."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_2_19_2","first-page":"3121","volume-title":"AISTATS","author":"Chatziafratis Vaggos","year":"2020","unstructured":"Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, and Mohammad Mahdian. 2020. Bisect and conquer: Hierarchical clustering via max-uncut bisection. In AISTATS, Vol. 108. 3121\u20133132."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_3_2_21_2","first-page":"219","volume-title":"STOC","author":"Chawla Shuchi","year":"2015","unstructured":"Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. 2015. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In STOC. 219\u2013228."},{"key":"e_1_3_2_22_2","first-page":"505","volume-title":"SIGMOD","author":"Cochez Michael","year":"2015","unstructured":"Michael Cochez and Hao Mou. 2015. Twister tries: Approximate hierarchical agglomerative clustering for average distance in linear time. In SIGMOD. 505\u2013517."},{"key":"e_1_3_2_23_2","volume-title":"ICML","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad, R\u00e9mi de Joannis de Verclos, and Guillaume Lagarde. 2021. Improving ultrametrics embeddings through coresets. In ICML."},{"key":"e_1_3_2_24_2","first-page":"6201","volume-title":"NeurIPS","author":"Cohen-Addad Vincent","year":"2017","unstructured":"Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Trenn. 2017. Hierarchical clustering beyond the worst-case. In NeurIPS. 6201\u20136209."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3321386"},{"key":"e_1_3_2_26_2","first-page":"2078","volume-title":"ICML","author":"Cohen-Addad Vincent","year":"2020","unstructured":"Vincent Cohen-Addad, Karthik C. S., and Guillaume Lagarde. 2020. On efficient low distortion ultrametric embedding. In ICML, Vol. 119. 2078\u20132088."},{"key":"e_1_3_2_27_2","article-title":"Correlation clustering with sherali-adams","author":"Cohen-Addad Vincent","year":"2022","unstructured":"Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman. 2022. Correlation clustering with sherali-adams. To appear FOCS\u201922 (2022), 651\u2013661.","journal-title":"To appear FOCS\u201922"},{"key":"e_1_3_2_28_2","first-page":"118","volume-title":"STOC","author":"Dasgupta Sanjoy","year":"2016","unstructured":"Sanjoy Dasgupta. 2016. A cost function for similarity-based hierarchical clustering. In STOC. 118\u2013127."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0092-8240(87)80007-1"},{"key":"e_1_3_2_30_2","first-page":"96","volume-title":"APPROX-RANDOM","author":"Dhamdhere Kedar","year":"2004","unstructured":"Kedar Dhamdhere. 2004. Approximating additive distortion of embeddings into line metrics. In APPROX-RANDOM. 96\u2013104."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_32_2","first-page":"25:1\u201325:22","volume-title":"SWAT","author":"Fan Chenglin","year":"2020","unstructured":"Chenglin Fan, Anna C. Gilbert, Benjamin Raichel, Rishi Sonthalia, and Gregory Van Buskirk. 2020. Generalized metric repair on graphs. In SWAT, Vol. 162. 25:1\u201325:22."},{"key":"e_1_3_2_33_2","first-page":"196","volume-title":"SODA","author":"Fan Chenglin","year":"2018","unstructured":"Chenglin Fan, Benjamin Raichel, and Gregory Van Buskirk. 2018. Metric violation distance: Hardness and approximation. In SODA. SIAM, 196\u2013209."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320212"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188585"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1086\/282802"},{"key":"e_1_3_2_37_2","first-page":"612","volume-title":"Allerton","author":"Gilbert Anna C.","year":"2017","unstructured":"Anna C. Gilbert and Lalit Jain. 2017. If it ain\u2019t broke, don\u2019t fix it: Sparse metric repair. In Allerton. IEEE, 612\u2013619."},{"key":"e_1_3_2_38_2","first-page":"313","volume-title":"Allerton","author":"Gilbert Anna C.","year":"2018","unstructured":"Anna C. Gilbert and Rishi Sonthalia. 2018. Unsupervised metric learning in presence of missing data. In Allerton. IEEE, 313\u2013321."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"e_1_3_2_41_2","first-page":"123","volume-title":"APPROX-RANDOM","author":"Harb Boulos","year":"2005","unstructured":"Boulos Harb, Sampath Kannan, and Andrew McGregor. 2005. Approximating the best-fit tree under l \\({}_{\\mbox{p}}\\) norms. In APPROX-RANDOM. 123\u2013133."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009268"},{"key":"e_1_3_2_43_2","volume-title":"Algorithm Design","author":"Kleinberg Jon M.","year":"2006","unstructured":"Jon M. Kleinberg and \u00c9va Tardos. 2006. Algorithm Design. Addison-Wesley."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009837726913"},{"key":"e_1_3_2_46_2","first-page":"3094","volume-title":"NeurIPS","author":"Moseley Benjamin","year":"2017","unstructured":"Benjamin Moseley and Joshua Wang. 2017. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In NeurIPS. 3094\u20133103."},{"key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1145\/1060590.1060645","volume-title":"STOC","author":"Mossel Elchanan","year":"2005","unstructured":"Elchanan Mossel and S\u00e9bastien Roch. 2005. Learning nonsingular phylogenies and hidden markov models. In STOC. 366\u2013375."},{"key":"e_1_3_2_48_2","first-page":"2316","volume-title":"NeurIPS","author":"Roy Aurko","year":"2016","unstructured":"Aurko Roy and Sebastian Pokutta. 2016. Hierarchical clustering via spreading metrics. In NeurIPS. 2316\u20132324."},{"key":"e_1_3_2_49_2","first-page":"670","volume-title":"SODA","author":"Sidiropoulos Anastasios","year":"2017","unstructured":"Anastasios Sidiropoulos, Dingkang Wang, and Yusu Wang. 2017. Metric embeddings with outliers. In SODA. 670\u2013689."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1038\/193855a0"},{"key":"e_1_3_2_51_2","volume-title":"Numerical Taxonomy. The Principles and Practice of Numerical Classification","author":"Sneath Peter H. A.","year":"1963","unstructured":"Peter H. A. Sneath and Robert R. Sokal. 1963. Numerical Taxonomy. The Principles and Practice of Numerical Classification. Freeman."},{"key":"e_1_3_2_52_2","volume-title":"NeurIPS","author":"Sonthalia Rishi","year":"2020","unstructured":"Rishi Sonthalia and Anna C. Gilbert. 2020. Tree! i am no tree! i am a low dimensional hyperbolic embedding. In NeurIPS."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0385"},{"key":"e_1_3_2_54_2","volume-title":"On the Computational Complexity of Inferring Evolutionary Trees","author":"Wareham Harold Todd","year":"1993","unstructured":"Harold Todd Wareham. 1993. On the Computational Complexity of Inferring Evolutionary Trees. Master\u2019s thesis. Memorial University of of Newfoundland."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(77)90351-4"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639453","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:53:37Z","timestamp":1750287217000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639453"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,10]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3639453"],"URL":"https:\/\/doi.org\/10.1145\/3639453","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2024,4,10]]},"assertion":[{"value":"2021-12-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}