Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

Request Changes to record.

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:
DateEvent
1999Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us