License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.4
URN: urn:nbn:de:0030-drops-146979
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14697/
Bhattacharya, Anup ;
Goyal, Dishant ;
Jaiswal, Ragesh
Hardness of Approximation for Euclidean k-Median
Abstract
The Euclidean k-median problem is defined in the following manner: given a set ? of n points in d-dimensional 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} ‖x-c‖₂ is minimized. The Euclidean k-means 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 k-means 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 k-median problem. In this work, assuming the unique games conjecture (UGC), we provide the hardness of approximation result for the Euclidean k-median 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 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. We show the hardness of bi-criteria approximation result for the Euclidean k-median problem for any β < 1.015, assuming UGC. We also show a similar hardness of bi-criteria approximation result for the Euclidean k-means 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 k-Median}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {4:1--4:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-207-5},
ISSN = {1868-8969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14697},
URN = {urn:nbn:de:0030-drops-146979},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.4},
annote = {Keywords: Hardness of approximation, bicriteria approximation, approximation algorithms, k-median, k-means}
}
|
Keywords: |
|
Hardness of approximation, bicriteria approximation, approximation algorithms, k-median, k-means |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
15.09.2021 |
