Improved Approximations for Ultrametric Violation Distance

Abstract

We study the Ultrametric Violation Distance problem introduced by Cohen-Addad, Fan, Lee, and Mesmay [FOCS, 2022]. Given pairwise distances $x\in {\mathbb{R}}_{>0}^{\left(\genfrac{}{}{0ex}{}{[n]}{2}\right)}$ 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 ${\ell }_0$ norm of the error; variants of the problem for the ${\ell }_{\infty }$ and ${\ell }_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 ($\ge 1000$) approximation algorithm. We give an $O(\min \{L,\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 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.

SODA 2024