Testing metric properties

Finite metric spaces, and in particular tree metrics play an important role in various disciplines such as evolutionary biology and statistics. A natural family of problems concerning metrics is deciding, given a matrix M , whether or not it is a distance metric of a certain predetermined type. Here we consider the following relaxed version of such decision problems: For any given matrix M and parameter \eps , we are interested in determining, by probing M , whether M has a particular metric property P , or whether it is ε far from having the property. In ε far we mean that more than an ε-fraction of the entries of M must be modified so that it obtains the property. The algorithm may query the matrix on entries M[i,j] of its choice, and is allowed a constant probability of error. We describe algorithms for testing Euclidean metrics, tree metrics and ultrametrics. Furthermore, we present an algorithm that tests whether a matrix M is an approximate ultrametric. In all cases the query complexity and running time are polynomial in 1 ε and independent of the size of the matrix. Finally, our algorithms can be used to solve relaxed versions of the corresponding search problems in time that is sub-linear in the size of the matrix.

Authors

• Michal Parnas
• Dana Ron

Keywords

No keywords are indexed for this paper.