On the approximability of numerical taxonomy (fitting distances by tree metrics)

被引：73

作者：

Agarwala, R

Bafna, V

Farach, M

Paterson, M

Thorup, M

机构：

[1] Rutgers State Univ, DIMACS, Piscataway, NJ 08855 USA

[2] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08855 USA

[3] Univ Warwick, Dept Comp Sci, Coventry CV4 7AL, W Midlands, England

[4] Univ Copenhagen, Dept Comp Sci, DK-2100 Copenhagen O, Denmark

来源：

SIAM JOURNAL ON COMPUTING | 1999年 / 28卷 / 03期

关键词：

approximation algorithm; tree metric; taxonomy;

D O I：

10.1137/S0097539795296334

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problem of fitting an n x n distance matrix D by a tree metric T. Let epsilon be the distance to the closest tree metric under the L-infinity norm; that is, epsilon = min(T) {parallel to T ? D parallel to infinity}. First we present an O(n(2)) algorithm for finding a tree metric T such that parallel to T ? D parallel to infinity less than or equal to 3 epsilon. Second we show that it is NP-hard to find a tree metric T such that parallel to T ? D parallel to infinity < 9/8 epsilon. This paper presents the first algorithm for this problem with a performance guarantee.

引用

页码：1073 / 1085

页数：13

共 10 条

[1]

Baire R., 1905, Lecons sur les fonctions discontinues

[2]

Barthelemy J.P., 1991, TREES PROXIMITY REPR

[3]

Buneman P., 1971, Mathematics in the Archeological and Historical Sciences, P387

[4] PHYLOGENETIC ANALYSIS - MODELS AND ESTIMATION PROCEDURES [J].