2026-07-24T18:02:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18723 2024-03-06T11:02:34Z ddc:004 open_access

Fitting Tree Metrics with Minimum Disagreements Kipouridis, Evangelos Hierarchical Clustering Tree Metrics Minimum Disagreements In the L₀ Fitting Tree Metrics problem, we are given all pairwise distances among the elements of a set V and our output is a tree metric on V. The goal is to minimize the number of pairwise distance disagreements between the input and the output. We provide an O(1) approximation for L₀ Fitting Tree Metrics, which is asymptotically optimal as the problem is APX-Hard. For p ≥ 1, solutions to the related L_p Fitting Tree Metrics have typically used a reduction to L_p Fitting Constrained Ultrametrics. Even though in FOCS '22 Cohen-Addad et al. solved L₀ Fitting (unconstrained) Ultrametrics within a constant approximation factor, their results did not extend to tree metrics. We identify two possible reasons, and provide simple techniques to circumvent them. Our framework does not modify the algorithm from Cohen-Addad et al. It rather extends any ρ approximation for L₀ Fitting Ultrametrics to a 6ρ approximation for L₀ Fitting Tree Metrics in a blackbox fashion. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Evangelos Kipouridis 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.70 urn:nbn:de:0030-drops-187233 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.70 eng https://creativecommons.org/licenses/by/4.0/legalcode