Metric Violation Distance: Hardness and Approximation.
Chenglin FanBenjamin RaichelGregory Van BuskirkPublished in: Algorithmica (2022)
Keyphrases
- distance measure
- distance function
- distance metric
- euclidean distance
- triangular inequality
- triangle inequality
- euclidean metric
- cosine distance
- mahalanobis distance
- manhattan distance
- hausdorff distance
- error bounds
- closed form
- information theoretic
- metric space
- approximation algorithms
- approximation methods
- approximation error
- absolute error
- dissimilarity measure
- similarity measure
- metric learning
- np complete
- np hard
- geodesic distance
- similarity metric
- relative error
- edit distance
- distance matrix
- distance transform
- approximation schemes
- error tolerance
- knn
- special case