4 papers · 1 filter
Faster and Simpler Greedy Algorithm for -Median and -Means
Max Dupré la Tour, David Saulpic
Clustering problems such as -means and -median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In…
Fully Dynamic k-Means Coreset in Near-Optimal Update Time
Max Dupré la Tour, Monika Henzinger, David Saulpic
We study in this paper the problem of maintaining a solution to -median and -means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently mai…
Making Old Things New: A Unified Algorithm for Differentially Private Clustering
Max Dupré la Tour, Monika Henzinger, David Saulpic
As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied under various privacy models. Centralized differential privacy is…
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…