Hardness of Approximation of Euclidean k-Median.
Anup BhattacharyaDishant GoyalRagesh JaiswalPublished in: CoRR (2020)
Keyphrases
- euclidean distance
- approximation algorithms
- approximation error
- error bounds
- np hard
- euclidean space
- computational complexity
- approximation methods
- np complete
- efficient computation
- phase transition
- constant factor approximation
- neural network
- square root
- median filter
- closed form
- worst case
- data points
- high dimensional
- multiscale