Hardness of Approximation of Euclidean k-Median
The Euclidean k-median problem is defined in the following manner: given a set π³ of n points in β^d, and an integer k, find a set C ββ^d of k points (called centers) such that the cost function Ξ¦(C,π³) β‘β_x βπ³min_c β Cx-c_2 is minimized. The Euclidean k-means problem is defined similarly by replacing the distance with squared distance in the cost function. Various hardness of approximation results are known for the Euclidean k-means problem. However, no hardness of approximation results were known for the Euclidean k-median problem. In this work, assuming the unique games conjecture (UGC), we provide the first hardness of approximation result for the Euclidean k-median problem. Furthermore, we study the hardness of approximation for the Euclidean k-means/k-median problems in the bi-criteria setting where an algorithm is allowed to choose more than k centers. That is, bi-criteria approximation algorithms are allowed to output Ξ² k centers (for constant Ξ²>1) and the approximation ratio is computed with respect to the optimal k-means/k-median cost. In this setting, we show the first hardness of approximation result for the Euclidean k-median problem for any Ξ² < 1.015, assuming UGC. We also show a similar bi-criteria hardness of approximation result for the Euclidean k-means problem with a stronger bound of Ξ² < 1.28, again assuming UGC.
READ FULL TEXT