Fitting Tree Metrics with 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.