TY - GEN

T1 - On the approximability of numerical taxonomy

AU - Agarwala, Richa

AU - Bafna, Vineet

AU - Farach, Martin

AU - Narayanan, Babu

AU - Paterson, Mike

AU - Thorup, Mikkel

PY - 1996/1/28

Y1 - 1996/1/28

N2 - We consider the problem of fitting an n × n distance matrix D by a tree metric T. Let ϵ be the distance to the closest tree metric under the L norm, that is, ϵ = minΓ {∥ T, D ∥∞}. First we present an O(n2) algorithm for finding an additive tree T such that ∥ T, D →∞, ≤ 3ϵ. Second we show that it is NP-hard to find a tree T such that ∥ T, D ∥∞ < 9/8ϵ. This paper presents the first algorithm for this problem with a performance guarantee.

AB - We consider the problem of fitting an n × n distance matrix D by a tree metric T. Let ϵ be the distance to the closest tree metric under the L norm, that is, ϵ = minΓ {∥ T, D ∥∞}. First we present an O(n2) algorithm for finding an additive tree T such that ∥ T, D →∞, ≤ 3ϵ. Second we show that it is NP-hard to find a tree T such that ∥ T, D ∥∞ < 9/8ϵ. This paper presents the first algorithm for this problem with a performance guarantee.

UR - http://www.scopus.com/inward/record.url?scp=84969399236&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969399236&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84969399236

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 365

EP - 372

BT - Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996

PB - Association for Computing Machinery

T2 - 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996

Y2 - 28 January 1996 through 30 January 1996

ER -