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

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. / Cohen-Addad, Vincent ; Das, Debarati; Kipouridis, Evangelos; Parotsidis, Nikos; Thorup, Mikkel.

2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. p. 1-12.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Cohen-Addad, V, Das, D, Kipouridis, E, Parotsidis, N & Thorup, M 2022, Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 1-12, 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021)), Virtual, 07/02/2022. https://doi.org/10.1109/FOCS52979.2021.00054

APA

Cohen-Addad, V., Das, D., Kipouridis, E., Parotsidis, N., & Thorup, M. (2022). Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (pp. 1-12). IEEE. https://doi.org/10.1109/FOCS52979.2021.00054

Vancouver

Cohen-Addad V, Das D, Kipouridis E, Parotsidis N, Thorup M. Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2022. p. 1-12 https://doi.org/10.1109/FOCS52979.2021.00054

Author

Cohen-Addad, Vincent ; Das, Debarati ; Kipouridis, Evangelos ; Parotsidis, Nikos ; Thorup, Mikkel. / Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. pp. 1-12

Bibtex

@inproceedings{8c947fcc979b4c14955ca4cd9929d494,
title = "Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor",
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{"}.",
author = "Vincent Cohen-Addad and Debarati Das and Evangelos Kipouridis and Nikos Parotsidis and Mikkel Thorup",
year = "2022",
doi = "10.1109/FOCS52979.2021.00054",
language = "English",
pages = "1--12",
booktitle = "2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)",
publisher = "IEEE",
note = "62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021)) ; Conference date: 07-02-2022 Through 11-02-2022",

}

RIS

TY - GEN

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

AU - Cohen-Addad, Vincent

AU - Das, Debarati

AU - Kipouridis, Evangelos

AU - Parotsidis, Nikos

AU - Thorup, Mikkel

PY - 2022

Y1 - 2022

N2 - 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".

AB - 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".

U2 - 10.1109/FOCS52979.2021.00054

DO - 10.1109/FOCS52979.2021.00054

M3 - Article in proceedings

SP - 1

EP - 12

BT - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021))

Y2 - 7 February 2022 through 11 February 2022

ER -

ID: 309113911