2026-07-21T20:03:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10649 2024-03-06T10:46:22Z ddc:004 open_access

Scalable and Jointly Differentially Private Packing Huang, Zhiyi Zhu, Xue Joint differential privacy packing scalable algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhiyi Huang and Xue Zhu 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.73 urn:nbn:de:0030-drops-106498 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.73 eng https://creativecommons.org/licenses/by/3.0/legalcode