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 proceedingArticle in proceedingsResearchpeer-review

7 Citations (Scopus)
14 Downloads (Pure)

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 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((logn)(loglogn)) by Ailon and Charikar [2005] who wrote "Determining whether an O(1) approximation can be obtained is a fascinating question".
Original languageEnglish
Title of host publication2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
PublisherIEEE
Publication date2022
Pages1-12
ISBN (Electronic)978-1-6654-2055-6
DOIs
Publication statusPublished - 2022
Event62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021)) - Virtual
Duration: 7 Feb 202211 Feb 2022

Conference

Conference62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021))
CityVirtual
Period07/02/202211/02/2022

Cite this