Improved Approximations for Ultrametric Violation Distance

Moses Charikar, Ruiquan Gao

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)}$ a…