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
Go to the corresponding LIPIcs Volume Portal

Huang, Zhiyi ; Zhu, Xue

Scalable and Jointly Differentially Private Packing

LIPIcs-ICALP-2019-73.pdf (0.5 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI