@inproceedings{10.5555/3600270.3602564,
author = {Mahpud, Bar and Sheffet, Or},
title = {A differentially private linear-time fPTAS for the minimum enclosing ball problem},
year = {2022},
isbn = {9781713871088},
publisher = {Curran Associates Inc.},
address = {Red Hook, NY, USA},
abstract = {The Minimum Enclosing Ball (MEB) problem is one of the most fundamental problems in clustering, with applications in operations research, statistics and computational geometry. In this works, we give the first linear time differentially private (DP) fPTAS for the Minimum Enclosing Ball problem, improving both on the runtime and the utility bound of the best known DP-PTAS for the problem, of Ghazi et al [21]. Given n points in ℝd that are covered by the ball B(θopt, ropt), our simple iterative DP-algorithm returns a ball B(θ, r) where r ≤ (1 + γ)ropt and which leaves at most $tilde O(frac{sqrt d}{gammaepsilon})$ points uncovered in $tilde O(n/gamma^2)$-time. We also give a local-model version of our algorithm, that leaves at most $tilde O(frac{sqrt {nd}}{gammaepsilon})$ points uncovered, improving on the n0.67-bound of Nissim and Stemmer [31] (at the expense of other parameters). Lastly, we test our algorithm empirically and discuss open problems.},
booktitle = {Proceedings of the 36th International Conference on Neural Information Processing Systems},
articleno = {2294},
numpages = {13},
location = {New Orleans, LA, USA},
series = {NIPS '22}
}