Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2024
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…
cs.DS2024
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…