Clustering with faulty centers

Joint work with Hongyao Huang, Benjamin Raichel

Computational Geometry: Theory and Applications (CGTA), 2023, special issue of invited papers from the 33rd International Symposium on Algorithms and Computation

pdf

Abstract

In this paper we introduce and formally study the problem of \(k\)-clustering with faulty centers. Specifically, we study the faulty versions of \(k\)-center, \(k\)-median, and \(k\)-means clustering, where centers have some probability of not existing, as opposed to prior work where clients had some probability of not existing. For all three problems we provide fixed parameter tractable algorithms, in the parameters \(k\), \(d\), and \(\varepsilon\), that \((1+\varepsilon)\)-approximate the minimum expected cost solutions for points in \(d\) dimensional Euclidean space. For Faulty \(k\)-center we additionally provide a \(5\)-approximation for general metrics. Significantly, all of our algorithms have a small dependence on \(n\). Specifically, our Faulty \(k\)-center algorithms have only linear dependence on \(n\), while for our algorithms for Faulty \(k\)-median and Faulty \(k\)-means the dependence is still only \(n^{1 + o(1)}\).

Extended abstract in Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC), 10:1–10:14, 2022.