We consider the problem of fitting an n × n distance matrix D by a tree metric T. Let ε be the distance to the closest tree metric under the L∞ norm; that is, ε=minT\∥ T-D∥∞\. First we present an O(n2 ) algorithm for finding a tree metric T such that ∥ T-D∥∞≤ 3ε. Second we show that it is NP-hard to find a tree metric T such that ∥ T-D∥∞ < 9/8ε. This paper presents the first algorithm for this problem with a performance guarantee.
No takes yet. Share an insight, caveat, or question.
Agarwala et al. (1998) studied this question.