Improved Approximations for Ultrametric Violation Distance
Moses Charikar, Ruiquan Gao · Society for Industrial and Applied Mathematics eBooks · 2024
We study the ultrametric violation distance problem introduced by Cohen-Addad, Fan, Lee, and Mesmay [FOCS, 2022]. Given pairwise distances 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 norm of the error; variants of the problem for the ℓ∞ and ℓ1 norms are well-studied in the literature.