Scalable and Jointly Differentially Private Packing

Abstract

We introduce an (\epsilon, \delta)-jointly differentially private algorithm for packing problems. Our algorithm not only achieves the optimal trade-off between the privacy parameter \epsilon 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.