File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611975031.24
- Scopus: eid_2-s2.0-85045541888
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update
Title | Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update |
---|---|
Authors | |
Issue Date | 2018 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, 7-10 January 2018, p. 343-357 How to Cite? |
Abstract | We present an improved (ε, δ-jointly differentially private algorithm for packing problems. Our algorithm gives a feasible output that is approximately optimal up to an αn additive factor as long as the supply of each resource is at least , where m is the number of resources. This improves the previous result by Hsu et al. (SODA ’16), which requires the total supply to be at least Õ(m2/αε), and only guarantees approximate feasibility in terms of total violation. Further, we complement our algorithm with an almost matching hardness result, showing that supply is necessary for any (ε, δ)-jointly differentially private algorithm to compute an approximately optimal packing solution. Finally, we introduce an alternative approach that runs in linear time, is exactly truthful, can be implemented online, and can be ε-jointly differentially private, but requires a larger supply of each resource. |
Persistent Identifier | http://hdl.handle.net/10722/251826 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Zhu, X | - |
dc.date.accessioned | 2018-03-19T07:01:51Z | - |
dc.date.available | 2018-03-19T07:01:51Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, 7-10 January 2018, p. 343-357 | - |
dc.identifier.isbn | 978-1-61197-503-1 | - |
dc.identifier.uri | http://hdl.handle.net/10722/251826 | - |
dc.description.abstract | We present an improved (ε, δ-jointly differentially private algorithm for packing problems. Our algorithm gives a feasible output that is approximately optimal up to an αn additive factor as long as the supply of each resource is at least , where m is the number of resources. This improves the previous result by Hsu et al. (SODA ’16), which requires the total supply to be at least Õ(m2/αε), and only guarantees approximate feasibility in terms of total violation. Further, we complement our algorithm with an almost matching hardness result, showing that supply is necessary for any (ε, δ)-jointly differentially private algorithm to compute an approximately optimal packing solution. Finally, we introduce an alternative approach that runs in linear time, is exactly truthful, can be implemented online, and can be ε-jointly differentially private, but requires a larger supply of each resource. | - |
dc.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | - |
dc.title | Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1137/1.9781611975031.24 | - |
dc.identifier.scopus | eid_2-s2.0-85045541888 | - |
dc.identifier.hkuros | 284473 | - |
dc.identifier.spage | 343 | - |
dc.identifier.epage | 357 | - |
dc.publisher.place | Philadelphia, PA | - |