论文标题
最小封闭球问题的差异私有线性时间FPTA
A Differentially Private Linear-Time fPTAS for the Minimum Enclosing Ball Problem
论文作者
论文摘要
最小封闭球（MEB）问题是聚类中最根本的问题之一，其应用在操作研究，统计和计算几何学中。在这项工作中，我们为最小封闭的球问题提供了第一个差异性私有（DP）FPTA，从而改善了Ghazi等人的运行时和最著名的DP-PTAS的实用性界限。 （2020）。给定的$ n $点在$ \ r^d $中被球$ b（θ_{opt}，r_ {opt}）$覆盖，我们的简单迭代dp-algorithm返回a球$ b（θ，r）$ r \ r \ r \ leq（1+γ）r_ {opt} $，以及最多的$ \ tilde o（s frac frac frac o（\ tilde o）。 d} {γε}）$点在$ \ tilde o（\ nicefrac n {γ^2}）$ - 时间。我们还提供了我们算法的本地模型版本，最多留下$ \ tilde o（\ frac {\ sqrt {nd}} {γε}）$点点了，从而改善了$ n^{0.67} $ - nissim and nissim and nissim and stemmer and stemmmer（2018）（2018）（extementess）。此外，我们从经验上测试我们的算法，并讨论未来的开放问题。
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\leq (1+γ)r_{opt}$ and which leaves at most $\tilde O(\frac{\sqrt d}{γε})$ points uncovered in $\tilde O(\nicefrac n {γ^2})$-time. We also give a local-model version of our algorithm, that leaves at most $\tilde O(\frac{\sqrt {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.
