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

Abstract

We consider the problem of fitting an n × n distance matrix D by a tree metric T. Let $\varepsilon$ be the distance to the closest tree metric under the $L_{\infty}$ norm; that is, $\varepsilon=\min_T\{\parallel T-D\parallel{\infty}\}$. First we present an O(n2 ) algorithm for finding a tree metric T such that $\parallel T-D\parallel{\infty}\leq 3\varepsilon$. Second we show that it is ${\cal NP}$-hard to find a tree metric T such that $\parallel T-D\parallel{\infty} < \frac{9}{8}\varepsilon$. This paper presents the first algorithm for this problem with a performance guarantee.