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

N1 - Funding Information: TDepartment of Computer Science, University of Warwick, Coventry CV4 7AL, UK. (msp@dcs.warwick.ac.uk) Supported in part by the ESPRIT Basic Research Action Programme of the EC under contract No. 7141 (project ALCOM II). Funding Information: IDIMACS, Rutgers University, Piscataway, NJ 08855, USA. (agarwala8dimacs.rutgers.edu) Supported by Special Year Na-tionel Science Foundation grant BIR-9412594. t(bafnaBdimacs.rutgera.edu) Supported by Specid Year National Science Foundation grant BIR-9412594. *Department of Computer Science, Rutgers University, Pis-cataway, NJ 08855, USA. (farach@cs.rutgers.edu, http://www.cs.nrtgers.edu/~farach) Supported by NSF Career Development Award CCR-9501942. f(bon@dimacs.rutgers.edu) Supportedby a DIMACS postdoctoral fellowship under grants STC-88-09648 and 91-19999.

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

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 -