On the approximability of numerical taxonomy
Richa Agarwala, Vineet Bafna, Babu O. Narayanan · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1996
We consider the problem of fitting an n {times} n distance matrix D by a tree metric T. Let {epsilon} be the distance to the closest tree metric under the L{sub {infinity}} norm, that is, {epsilon} = min{sub T} ({parallel}T, D{parallel}{sub {infinity}}). First we present an O(n{sup 2}) algorithm for finding an additive tree T such that {parallel}T, D {parallel}{sub {infinity}} {le} 3{epsilon}. Second we show that it is NP-hard to find a tree T such that {parallel} T, D {parallel} {sub {infinity}} < 9/8{epsilon}. This paper presents the first algorithm for this problem with a performance guarantee.