A Differentially Private Linear-Time fPTAS for the Minimum Enclosing Ball Problem

2022/06/07 by Mahpud, Bar, Sheffet, Or
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2206.03319

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 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. (2020). Given n points in \R^d that are covered by the ball B(θ_opt,r_opt), our simple iterative DP-algorithm returns a ball B(θ,r) where r≤ (1+γ)r_opt and which leaves at most O((√ d)/(γε)) points uncovered in O(\nicefrac n γ²)-time. We also give a local-model version of our algorithm, that leaves at most O(\frac√ ndγε) points uncovered, improving on the n^0.67-bound of Nissim and Stemmer (2018) (at the expense of other parameters). In addition, we test our algorithm empirically and discuss future open problems.

Related

• Clustering Algorithms for the Centralized and Local Models
• Minimum Enclosing Ball Revisited: Stability and Sub-linear Time Algorithms
• New Approximation Algorithms for Minimum Enclosing Convex Shapes
• A branch-and-bound algorithm for the minimum radius k-enclosing ball problem
• Towards the mathematical foundation of the minimum enclosing ball and related problems