License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.73
URN: urn:nbn:de:0030-drops-106498
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10649/
Huang, Zhiyi ;
Zhu, Xue
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.
BibTeX - Entry
@InProceedings{huang_et_al:LIPIcs:2019:10649,
author = {Zhiyi Huang and Xue Zhu},
title = {{Scalable and Jointly Differentially Private Packing}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {73:1--73:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10649},
URN = {urn:nbn:de:0030-drops-106498},
doi = {10.4230/LIPIcs.ICALP.2019.73},
annote = {Keywords: Joint differential privacy, packing, scalable algorithms}
}
|
Keywords: |
|
Joint differential privacy, packing, scalable algorithms |
|
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.07.2019 |
