Abstract
This paper presents universal algorithms for clustering problems, including the widely studied kmedian, kmeans, and kcenter objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solution sol for a clustering problem is said to be an (α, β)approximation if for all subsets of clients C', it satisfies sol(C') ≤ α ⋅ opt(C') + β ⋅ mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution.
Our main results are universal algorithms for the standard clustering objectives of kmedian, kmeans, and kcenter that achieve (O(1), O(1))approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other ?_pobjectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)approximation is NPhard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O(1))approximation is the strongest type of guarantee obtainable for universal clustering.
BibTeX  Entry
@InProceedings{ganesh_et_al:LIPIcs.ICALP.2021.70,
author = {Ganesh, Arun and Maggs, Bruce M. and Panigrahi, Debmalya},
title = {{Universal Algorithms for Clustering Problems}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {70:170:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14139},
URN = {urn:nbn:de:0030drops141397},
doi = {10.4230/LIPIcs.ICALP.2021.70},
annote = {Keywords: universal algorithms, clustering, kmedian, kmeans, kcenter}
}
Keywords: 

universal algorithms, clustering, kmedian, kmeans, kcenter 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 