Improved Approximations for Ultrametric Violation Distance

We study the Ultrametric Violation Distance problem introduced by Cohen-Addad, Fan, Lee, and Mesmay [FOCS, 2022]. Given pairwise distances x ∈ R ( [n] 2 ) >0 as input, the goal is to modify the minimum number of distances so as to make it a valid ultrametric. In other words, this is the problem of fitting an ultrametric to given data, where the quality of the fit is measured by the ℓ 0 norm of the error; variants of the problem for the ℓ ∞ and ℓ 1 norms are well-studied in the literature.

Our main result is a 5-approximation algorithm for Ultrametric Violation Distance, improving the previous best large constant factor (≥ 1000) approximation algorithm. We give an O(minL, log n)-approximation for weighted Ultrametric Violation Distance where the weights satisfy triangle inequality and L is the number of distinct values in the input. We also give a 16-approximation algorithm for the problem on k-partite graphs, where the input is specified on pairs of vertices that form a complete k-partite graph. All our results use a unified algorithmic framework with small modifications for the three cases.