License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09511.6
URN: urn:nbn:de:0030-drops-24986
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2498/
|
Go to the corresponding Portal |
Talwar, Kunal ;
Gupta, Anupam ;
Ligett, Katrina ;
McSherry, Frank ;
Roth, Aaron
Differentially Private Combinatorial Optimization
Abstract
Consider the following problem: given a metric space, some of whose points are ``clients,'' select a set of at most $k$ facility locations to minimize the average distance from the clients to their nearest facility. This is just the well-studied $k$-median problem, for which many approximation algorithms and hardness results are known. Note that the objective function encourages opening facilities in areas where there are many clients, and given a solution, it is often possible to get a good idea of where the clients are located. This raises the following quandary: what if the locations of the clients are sensitive information that we would like to keep private? emph{Is it even possible to design good algorithms for this problem that preserve the privacy of the clients?}
In this paper, we initiate a systematic study of algorithms for discrete optimization problems in the framework of differential privacy (which formalizes the idea of protecting the privacy of individual input elements). We show that many such problems indeed have good approximation algorithms that preserve differential privacy; this is even in cases where it is impossible to preserve cryptographic definitions of privacy while computing any non-trivial approximation to even the emph{value} of an optimal solution, let alone the entire solution.
Apart from the $k$-median problem, we consider the problems of vertex and set cover, min-cut, facility location, and Steiner tree, and give approximation algorithms and lower bounds for these problems. We also consider the recently introduced submodular maximization problem, ``Combinatorial Public Projects'' (CPP), shown by Papadimitriou et al. cite{PSS08} to be inapproximable to subpolynomial multiplicative factors by any efficient and emph{truthful} algorithm. We give a differentially private (and hence approximately truthful) algorithm that achieves a logarithmic additive approximation.
Joint work with Anupam Gupta, Katrina Ligett, Frank McSherry and Aaron Roth.
BibTeX - Entry
@InProceedings{talwar_et_al:DagSemProc.09511.6,
author = {Talwar, Kunal and Gupta, Anupam and Ligett, Katrina and McSherry, Frank and Roth, Aaron},
title = {{Differentially Private Combinatorial Optimization}},
booktitle = {Parameterized complexity and approximation algorithms},
pages = {1--31},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2010},
volume = {9511},
editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2010/2498},
URN = {urn:nbn:de:0030-drops-24986},
doi = {10.4230/DagSemProc.09511.6},
annote = {Keywords: Differential Privacy, Approximation Algorithms}
}
|
Keywords: |
|
Differential Privacy, Approximation Algorithms |
|
Collection: |
|
09511 - Parameterized complexity and approximation algorithms |
|
Issue Date: |
|
2010 |
|
Date of publication: |
|
02.03.2010 |
