Scalable and Jointly Differentially Private Packing
Zhiyi Huang, Xue You Zhu · arXiv (Cornell University) · 2019
We introduce an $(ε, δ)$-jointly differentially private algorithm for packing problems. Our algorithm not only achieves the optimal trade-off between the privacy parameter $ε$ and the minimum supply requirement (up to logarithmic factors), but is also scalable in the sense that the running time is linear in the number of agents $n$. Previous algorithms either run in cubic time in $n$, or require a minimum supply per resource that is $\sqrt{n}$ times larger than the best possible.