Fitting Tree Metrics with Minimum Disagreements
share
In the L_0 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_0 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_0 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_0 Fitting Ultrametrics to a 6ρ approximation for L_0 Fitting Tree Metrics in a blackbox fashion.
READ FULL TEXT