On the approximability of numerical taxonomy

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

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 proceeding › Conference contribution

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(n²) 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 language	English (US)
Title of host publication	Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
Publisher	Association for Computing Machinery
Pages	365-372
Number of pages	8
ISBN (Electronic)	0898713668
State	Published - Jan 28 1996
Event	7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996 - Atlanta, United States Duration: Jan 28 1996 → Jan 30 1996

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	Part F129447

Conference

Conference	7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
Country/Territory	United States
City	Atlanta
Period	1/28/96 → 1/30/96

ASJC Scopus subject areas

Software
General Mathematics

Cite this

On the approximability of numerical taxonomy. / Agarwala, Richa; Bafna, Vineet; Farach, Martin et al.
Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996. Association for Computing Machinery, 1996. p. 365-372 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. Part F129447).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Agarwala, R, Bafna, V, Farach, M, Narayanan, B, Paterson, M & Thorup, M 1996, On the approximability of numerical taxonomy. in Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. Part F129447, Association for Computing Machinery, pp. 365-372, 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996, Atlanta, United States, 1/28/96.

@inproceedings{f680b7efed614c95a8bcc1d76974151b,

title = "On the approximability of numerical taxonomy",

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

author = "Richa Agarwala and Vineet Bafna and Martin Farach and Babu Narayanan and Mike Paterson and Mikkel Thorup",

year = "1996",

month = jan,

day = "28",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "365--372",

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

note = "7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996 ; Conference date: 28-01-1996 Through 30-01-1996",

}

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 -

On the approximability of numerical taxonomy

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this