Skip to main content

Universal Algorithms for Clustering Problems

Publication ,  Journal Article
Ganesh, A; Maggs, BM; Panigrahi, D
Published in: ACM Transactions on Algorithms
March 9, 2023

This article presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center 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 k-median, k-means, and k-center 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 ĝ.,"p-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)-approximation is NP-hard 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.

Duke Scholars

Published In

ACM Transactions on Algorithms

DOI

EISSN

1549-6333

ISSN

1549-6325

Publication Date

March 9, 2023

Volume

19

Issue

2

Related Subject Headings

  • Computation Theory & Mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 4605 Data management and data science
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Ganesh, A., Maggs, B. M., & Panigrahi, D. (2023). Universal Algorithms for Clustering Problems. ACM Transactions on Algorithms, 19(2). https://doi.org/10.1145/3572840
Ganesh, A., B. M. Maggs, and D. Panigrahi. “Universal Algorithms for Clustering Problems.” ACM Transactions on Algorithms 19, no. 2 (March 9, 2023). https://doi.org/10.1145/3572840.
Ganesh A, Maggs BM, Panigrahi D. Universal Algorithms for Clustering Problems. ACM Transactions on Algorithms. 2023 Mar 9;19(2).
Ganesh, A., et al. “Universal Algorithms for Clustering Problems.” ACM Transactions on Algorithms, vol. 19, no. 2, Mar. 2023. Scopus, doi:10.1145/3572840.
Ganesh A, Maggs BM, Panigrahi D. Universal Algorithms for Clustering Problems. ACM Transactions on Algorithms. 2023 Mar 9;19(2).

Published In

ACM Transactions on Algorithms

DOI

EISSN

1549-6333

ISSN

1549-6325

Publication Date

March 9, 2023

Volume

19

Issue

2

Related Subject Headings

  • Computation Theory & Mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 4605 Data management and data science
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics