On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)

. We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric under the L1 norm, that is, " = minT fk T \Gamma D k1g. First we present an O(n 2 ) algorithm for finding a tree metric T such that k T \Gamma D k1 3". Second we show that it is NP-hard to find a tree metric T such that k T \Gamma D k1 ! 9 8 ". This paper presents the first algorithm for this problem with a performance guarantee. Key words. Approximation algorithm, tree metric, taxonomy. AMS subject classifications. 62P10, 68Q25, 92B10, 92-08. 1. Introduction. One of the most common methods for clustering numeric data involves fitting the data to a tree metric, which is defined by a weighted tree spanning the points of the metric, the distance between two points being the sum of the weights of the edges of the path between them. Not surprisingly, this problem, the so-called Numerical Taxonomy problem, has received a great deal of attention ..