# Clustering Algorithms for the Centralized and Local Models

arXiv: https://arxiv.org/abs/1707.04766 · HTML: https://mlsanity.com/paper/1707.04766/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2017.

## Built on by (most cited first, 18 of 18)

- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Differentially Private Vertical Federated Clustering](https://mlsanity.com/paper/2208.01700/) (2022)
- [Data-adaptive Differentially Private Prompt Synthesis for In-Context Learning](https://mlsanity.com/paper/2410.12085/) (2024)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [Differentially-Private Sublinear-Time Clustering](https://mlsanity.com/paper/2112.13751/) (2021)
- [FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy](https://mlsanity.com/paper/2405.02437/) (2024)
- [Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error](https://mlsanity.com/paper/2105.15007/) (2021)
- [Differentially Private Algorithms for Clustering with Stability Assumptions](https://mlsanity.com/paper/2106.12959/) (2021)
- [Locally Differentially Private Distributed Deep Learning via Knowledge Distillation](https://mlsanity.com/paper/2202.02971/) (2022)
- [DPM: Clustering Sensitive Data through Separation](https://mlsanity.com/paper/2307.02969/) (2023)
- [Differentially Private Clustering in Data Streams](https://mlsanity.com/paper/2307.07449/) (2023)
- [Contrastive Explainable Clustering with Differential Privacy](https://mlsanity.com/paper/2406.04610/) (2024)
- [A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input](https://mlsanity.com/paper/2505.14251/) (2025)
- [Differentially Private Federated Clustering with Random Rebalancing](https://mlsanity.com/paper/2508.06183/) (2025)
- [PE-means: Improved Differentially Private k-means Clustering through Private Evolution](https://mlsanity.com/paper/2606.00342/) (2026)

## Abstract (arXiv)

We revisit the problem of finding a minimum enclosing ball with differential privacy: Given a set of n points in the Euclidean space ℝd and an integer t≤ n, the goal is to find a ball of the smallest radius ropt enclosing at least t input points. The problem is motivated by its various applications to differential privacy, including the sample and aggregate technique, private data exploration, and clustering. Without privacy concerns, minimum enclosing ball has a polynomial time approximation scheme (PTAS), which computes a ball of radius almost ropt (the problem is NP-hard to solve exactly). In contrast, under differential privacy, until this work, only a O(√log n)-approximation algorithm was known. We provide new constructions of differentially private algorithms for minimum enclosing ball achieving constant factor approximation to ropt both in the centralized model (where a trusted curator collects the sensitive information and analyzes it with differential privacy) and in the local model (where each respondent randomizes her answers to the data curator to protect her privacy). We demonstrate how to use our algorithms as a building block for approximating k-means in both models.