On the approximability of numerical taxonomy

Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
PublisherAssociation for Computing Machinery
Pages365-372
Number of pages8
ISBN (Electronic)0898713668
StatePublished - Jan 28 1996
Event7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996 - Atlanta, United States
Duration: Jan 28 1996Jan 30 1996

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
VolumePart F129447

Other

Other7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
Country/TerritoryUnited States
CityAtlanta
Period1/28/961/30/96

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'On the approximability of numerical taxonomy'. Together they form a unique fingerprint.

Cite this