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
ABSTRACT
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