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

Richa Agarwala; Vineet Bafna; Martin Farach; Mike Paterson; Mikkel Thorup

doi:10.1137/s0097539795296334

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

Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup

Research output: Contribution to journal › Article › peer-review

Abstract

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, ε = min_T{∥ T -D ∥ ∞}. First we present an O(n²) 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.

Original language	English (US)
Pages (from-to)	1073-1085
Number of pages	13
Journal	SIAM Journal on Computing
Volume	28
Issue number	3
DOIs	https://doi.org/10.1137/s0097539795296334
State	Published - 1999

Keywords

Approximation algorithm
Taxonomy
Tree metric

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/s0097539795296334

Cite this

@article{0cfb81929e244ff8b7655d2c684e15d1,

title = "On the approximability of numerical taxonomy (fitting distances by tree metrics)",

abstract = "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.",

keywords = "Approximation algorithm, Taxonomy, Tree metric",

author = "Richa Agarwala and Vineet Bafna and Martin Farach and Mike Paterson and Mikkel Thorup",

year = "1999",

doi = "10.1137/s0097539795296334",

language = "English (US)",

volume = "28",

pages = "1073--1085",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

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

AU - Agarwala, Richa

AU - Bafna, Vineet

AU - Farach, Martin

AU - Paterson, Mike

AU - Thorup, Mikkel

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Taxonomy

KW - Tree metric

UR - http://www.scopus.com/inward/record.url?scp=0032256591&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032256591&partnerID=8YFLogxK

U2 - 10.1137/s0097539795296334

DO - 10.1137/s0097539795296334

M3 - Article

AN - SCOPUS:0032256591

SN - 0097-5397

VL - 28

SP - 1073

EP - 1085

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this