Consider the following problem: given a metric space, some of whose points are "clients", open a set of at most @math facilities to minimize the average distance from the clients to these facilities. This is just the well-studied @math -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. However, this poses the following quandary: what if the identity of the clients is sensitive information that we would like to keep private? 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_value_ of an optimal solution, let alone the entire solution. Apart from the @math -median problem, we study the problems of vertex and set cover, min-cut, facility location, Steiner tree, and the recently introduced submodular maximization problem, "Combinatorial Public Projects" (CPP).
@cite_24: The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in the usual sense, but does not yield any information on x other than what can be deduced from f(x) . As such, F(x) is useful for private computation of f(x) (assuming that F can be computed more efficiently than f . In this work we examine the properties and limitations of this new notion. Specifically, we show that for many NP-hard problems, the privacy requirement precludes non-trivial approximation. This is the case even for problems that otherwise admit very good approximation (e.g., problems with PTAS). On the other hand, we show that slightly relaxing the privacy requirement, by means of leaking “just a few bits of informationrdquo; about x , again permits good approximation.
@cite_26: 
@cite_11: Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and may be extremely large. Furthermore, for some applications, the parties want to compute a function of their inputs securely without revealing more information than necessary. In this work, we study the question of simultaneously addressing the above efficiency and security concerns via what we call secure approximations.We start by extending standard definitions of secure (exact) computation to the setting of secure approximations. Our definitions guarantee that no additional information is revealed by the approximation beyond what follows from the output of the function being approximated. We then study the complexity of specific secure approximation problems. In particular, we obtain a sublinear-communication protocol for securely approximating the Hamming distance and a polynomial-time protocol for securely approximating the permanent and related #P-hard problems.
Nonetheless, @cite_11 and others show a number of positive approximation results under versions of the functional privacy model. @cite_24 provide positive results in the function privacy setting when the algorithm is permitted to leak few bits (each equivalence class of input need not produce identical output, but must be one of at most @math possible outcomes). Indyk and Woodruff also give some positive results for the approximation of @math distance and a nearest neighbor problem @cite_26 . However, as functional privacy extends SFE, it does not protect sensitive data that can be inferred from the output.