Differentially Private Combinatorial Optimization

Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar

[PDF]

We consider a number of combinatorial optimization problems, for which the algorithm is constrained to preserve the privacy of its input while still giving good approximation guarantees. For k-median, vertex-cover, set-cover, min-cut, facility location, Steiner Tree, and the recently introduced "Combinatorial Public Projects" (CPP) problem, we give efficient privacy-preserving approximation algorithms, as well as optimal information theoretic upper and lower bounds. All of our algorithms also imply efficiently computable approximately-truthful mechanisms. In particular, we get an efficient approximately truthful mechanism for the CPP problem that achieves a much better approximation ratio than can be achieved efficiently by any exactly truthful mechanism.