Abstract
The Euclidean kmedian problem is defined in the following manner: given a set ? of n points in ddimensional Euclidean space ℝ^d, and an integer k, find a set C ⊂ ℝ^d of k points (called centers) such that the cost function Φ(C,?) ≡ ∑_{x ∈ ?} min_{c ∈ C} ‖xc‖₂ is minimized. The Euclidean kmeans problem is defined similarly by replacing the distance with squared Euclidean distance in the cost function. Various hardness of approximation results are known for the Euclidean kmeans problem [Pranjal Awasthi et al., 2015; Euiwoong Lee et al., 2017; Vincent Cohen{}Addad and {Karthik {C. S.}}, 2019]. However, no hardness of approximation result was known for the Euclidean kmedian problem. In this work, assuming the unique games conjecture (UGC), we provide the hardness of approximation result for the Euclidean kmedian problem in O(log k) dimensional space. This solves an open question posed explicitly in the work of Awasthi et al. [Pranjal Awasthi et al., 2015].
Furthermore, we study the hardness of approximation for the Euclidean kmeans/kmedian problems in the bicriteria setting where an algorithm is allowed to choose more than k centers. That is, bicriteria approximation algorithms are allowed to output β k centers (for constant β > 1) and the approximation ratio is computed with respect to the optimal kmeans/kmedian cost. We show the hardness of bicriteria approximation result for the Euclidean kmedian problem for any β < 1.015, assuming UGC. We also show a similar hardness of bicriteria approximation result for the Euclidean kmeans problem with a stronger bound of β < 1.28, again assuming UGC.
BibTeX  Entry
@InProceedings{bhattacharya_et_al:LIPIcs.APPROX/RANDOM.2021.4,
author = {Bhattacharya, Anup and Goyal, Dishant and Jaiswal, Ragesh},
title = {{Hardness of Approximation for Euclidean kMedian}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {4:14:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14697},
URN = {urn:nbn:de:0030drops146979},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.4},
annote = {Keywords: Hardness of approximation, bicriteria approximation, approximation algorithms, kmedian, kmeans}
}
Keywords: 

Hardness of approximation, bicriteria approximation, approximation algorithms, kmedian, kmeans 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) 
Issue Date: 

2021 
Date of publication: 

15.09.2021 