DIMACS TR: 95-46

On the Approximability of Numerical Taxonomy

Fitting Distances by Tree Metrics

Authors: Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup


We consider the problem of fitting an nxn distance matrix D by a tree metric T. Let e be the distance to the closest tree metric, that is, e=min_T |,D|_infinity. First we present an O(n^2) algorithm for finding an additive tree T such that |T,D|_infinity <= 3e. Second we show that it is NP-hard to find a tree T such that |T,D|_infinity < 9/8 e. This paper presents the first algorithm for this problem with a performance guarantee.

Note: Richa Agarwala and Vineet Bafna were supported by DIMACS Special Year National Science Foundation grant BIR-9412594 and Babu Narayanan was supported by a DIMACS postdoctoral fellowship under grants STC-88-09648 and 91-19999.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-46.ps.gz

DIMACS Home Page