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 (1997) On the approximability of numerical taxonomy (fitting distances by tree metrics). University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-330.pdf - Other - Requires a PDF viewer. Download (1104Kb) | Preview |
Abstract
We consider the problem of fitting an n x n distance matrix D by a tree metric T. Let e be the distance to the closest tree metric under the L[infinity] norm, that is e=minT{||T-D||[infinity]}. First we present an O(n2) algorithm for finding a tree metric T such that ||T-D||[infinity] <= 3e. Second we show that it is NP-hard to find a tree metric T such that ||T-D||inf <= 9e/8. This paper presents the first algorithm for this problem with a performance guarantee.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Trees (Graph theory), Numerical taxonomy | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | July 1997 | ||||
| Dates: |
|
||||
| Number: | Number 330 | ||||
| Number of Pages: | 14 | ||||
| DOI: | CS-RR-330 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | R. Ararwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson and M. Thorup, M. “On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)”, <i>Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms</i>, ACM/SIAM, New York, NY, pp. 365-372 (1996) | ||||
| Funder: | National Science Foundation (U.S.) (NSF), European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | BIR-9412594 (NSF), CCR-9501942 (NSF), 20244 (ESPRIT) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
