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

Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the numerical taxonomy problem of fitting a positive distance function D: (S2) → 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 thebranching 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.”

Original languageEnglish (US)
Article number10
JournalJournal of the ACM
Volume71
Issue number2
DOIs
StatePublished - Apr 10 2024

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor'. Together they form a unique fingerprint.

Cite this