3 papers
cs.DS2023
Experimental Evaluation of Fully Dynamic k-Means via Coresets
Monika Henzinger, David Saulpic, Leonhard Sidl
For a set of points in , the Euclidean -means problems consists of finding centers such that the sum of distances squared from each data point to its closest c…
cs.DS2023
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key rol…
cs.DS2023
Differential Privacy for Clustering Under Continual Observation
Max Dupré la Tour, Monika Henzinger, David Saulpic
We consider the problem of clustering privately a dataset in that undergoes both insertion and deletion of points. Specifically, we give an -differentia…