Hardness of Approximation for Euclidean k-Median.

Anup Bhattacharya Dishant Goyal Ragesh Jaiswal

Published in: APPROX-RANDOM (2021)

Keyphrases

euclidean space
approximation algorithms
np hard
approximation error
constant factor approximation
median filter
phase transition
closed form
euclidean distance
computational complexity
error bounds
relative error
half spaces
worst case
website
euclidean metric
database