The Library
On the approximability of numerical taxonomy (fitting distances by tree metrics)
Tools
Tools
Tools
Agarwala, Richa, Bafna, Vineet, Farach, Martin, Paterson, Michael S. and Thorup, Mikkel (1999) On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM Journal on Computing, Volume 28 (Number 3). pp. 1073-1085.
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1137/S0097539795296334
Abstract
We consider the problem of fitting an n x n distance matrix D by a tree metric T. Let epsilon be the distance to the closest tree metric under the L-infinity norm; that is, epsilon = min(T) {parallel to T ? D parallel to infinity}. First we present an O(n(2)) algorithm for finding a tree metric T such that parallel to T ? D parallel to infinity less than or equal to 3 epsilon. Second we show that it is NP-hard to find a tree metric T such that parallel to T ? D parallel to infinity < 9/8 epsilon. This paper presents the first algorithm for this problem with a performance guarantee.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Alternative Title: | |||||
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||
| ISSN: | 0097-5397 | ||||
| Official Date: | 1999 | ||||
| Dates: |
|
||||
| Volume: | Volume 28 | ||||
| Number: | Number 3 | ||||
| Number of Pages: | 13 | ||||
| Page Range: | pp. 1073-1085 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
