# Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

arXiv: https://arxiv.org/abs/2110.02807 · HTML: https://mlsanity.com/paper/2110.02807/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2021.

## Built on by (most cited first, 3 of 3)

- [HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering](https://mlsanity.com/paper/2205.09721/) (2022)
- [Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams](https://mlsanity.com/paper/2311.17840/) (2023)
- [Fitting trees to ℓ1-hyperbolic distances](https://mlsanity.com/paper/2409.01010/) (2024)

## Abstract (arXiv)

We consider the numerical taxonomy problem of fitting a positive distance function D:Schoose 2rightarrow mathbb R>0 by a tree metric. We want a tree T with positive edge weights and including S among the vertices so that their distances in T match those in D. A nice application is in evolutionary biology where the tree T aims to approximate the branching process leading to the observed distances in D [Cavalli-Sforza and Edwards 1967]. We consider the total error, that is the sum of distance errors over all pairs of points. We present a deterministic polynomial time algorithm minimizing the total error within a constant factor. We can do this both for general trees, and for the special case of ultrametrics with a root having the same distance to all vertices in S. The problems are APX-hard, so a constant factor is the best we can hope for in polynomial time. The best previous approximation factor was O((log n)(log log n)) by Ailon and Charikar [2005] who wrote "Determining whether an O(1) approximation can be obtained is a fascinating question".