Metric Violation Distance: Hardness and Approximation.
Chenglin FanBenjamin RaichelGregory Van BuskirkPublished in: SODA (2018)
Keyphrases
- distance measure
- distance function
- distance metric
- triangular inequality
- triangle inequality
- euclidean distance
- cosine distance
- euclidean metric
- hausdorff distance
- mahalanobis distance
- dissimilarity measure
- satisfy the triangle inequality
- manhattan distance
- approximation algorithms
- distance matrix
- euclidean norm
- edit distance
- similarity search
- nearest neighbor
- neural network
- error bounds
- evaluation metrics
- continuous functions
- metric space
- absolute error
- np complete
- worst case
- probability distribution
- computational complexity