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: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We consider the numerical taxonomy problem of fitting a positive distance function D}:\binom{S2rightarrow 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'.

Original languageEnglish (US)
Title of host publicationProceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PublisherIEEE Computer Society
Pages468-479
Number of pages12
ISBN (Electronic)9781665420556
DOIs
StatePublished - 2022
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: Feb 7 2022Feb 10 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-February
ISSN (Print)0272-5428

Conference

Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period2/7/222/10/22

All Science Journal Classification (ASJC) codes

  • General Computer Science

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