The Library
On the approximability of numerical taxonomy (fitting distances by tree metrics)
Tools
Tools
Tools
UNSPECIFIED (1999) On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM JOURNAL ON COMPUTING, 28 (3). pp. 1073-1085. ISSN 0097-5397
Full text not available from this repository.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 |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
| Journal or Publication Title: | SIAM JOURNAL ON COMPUTING |
| Publisher: | SIAM PUBLICATIONS |
| ISSN: | 0097-5397 |
| Date: | 19 March 1999 |
| Volume: | 28 |
| Number: | 3 |
| Number of Pages: | 13 |
| Page Range: | pp. 1073-1085 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/14674 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
