Answers are grounded in this paper and cite their sources.
We consider the numerical taxonomy problem of fitting a positive distance function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D:S2→ R> 0</tex> by a tree metric. We want a tree <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</tex> with positive edge weights and including <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</tex> among the vertices so that their distances in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</tex> match those in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</tex> . A nice application is in evolutionary biology where the tree <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</tex> aims to approximate the branching process leading to the observed distances in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</tex> [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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</tex> . 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O((log n)(loglog n)</tex> ) by Ailon and Charikar [2005] who wrote “Determining whether an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(1)$</tex> approximation can be obtained is a fascinating question”.
No takes yet. Share an insight, caveat, or question.
Cohen-Addad et al. (2022) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: