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_11 extend the notion of SFE to NP hard problems for which efficient algorithms must output an approximation to the optimum, unless P=NP. They defined as functional privacy the constraint that two inputs with the same output value (e.g. the size of an optimal vertex cover) must produce the same value under the approximation algorithm. Under this constraint, @cite_24 show that approximating the value of vertex cover to within @math is as hard as computing the value itself, for any constant @math . These hardness results were extended to search problems by @cite_19 , where the constraint is relaxed to only equate those inputs whose sets of optimal solutions are identical. These results were extended and strengthened by @cite_6 @cite_21 .
@cite_21 @cite_6 @cite_24 @cite_19 @cite_11
2001663593 1855768119 1749371477 2116953739
par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degreeror bounded “width.” Specifically: We prove that the Max 3SAT problem on instances where each variable occurs in at most B clauses, is hard to approximate to within a factor @math , unless @math . H stad [18] proved that the problem is approximable to within a factor @math in polynomial time, and that is hard to approximate to within a factor @math . Our result uses a new randomized reduction from general instances of Max 3SAT to bounded-occurrences instances. The randomized reduction applies to other Max SNP problems as well. We observe that the Set Cover problem on instances where each set has size at most B is hard to approximate to within a factor @math unless @math . The result follows from an appropriate setting of parameters in Feige's reduction [11]. This is essentially tight in light of the existence of @math -approximate algorithms [20, 23, 9] We present a new PCP construction, based on applying parallel repetition to the inner verifier,'' and we provide a tight analysis for it. Using the new construction, and some modifications to known reductions from PCP to Hitting Set, we prove that Hitting Set with sets of size B is hard to approximate to within a factor @math . The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B =2. The relationship between hardness of approximation and set size seems to have not been explored before. We observe that the Independent Set problem on graphs having degree at most B is hard to approximate to within a factor @math , unless P = NP . This follows from a comination of results by Clementi and Trevisan [28] and Reingold, Vadhan and Wigderson [27]. It had been observed that the problem is hard to approximate to within a factor @math unless P = NP [1]. An algorithm achieving factor @math is also known [21, 2, 30, 16 . A vertex cover of a graph is a subset of vertices such that each edge has at least one endpoint in the subset. Determining the minimum vertex cover is a well-known NP-complete problem in a sequential setting. Several techniques, e.g., depth-first search, a local ratio theorem, and semidefinite relaxation, have given good approximation algorithms. However, some of them cannot be applied to a distributed setting, in particular self-stabilizing algorithms. Thus only a 2-approximation solution based on a self-stabilizing maximal matching has been obviously known until now. In this paper we propose a new self-stabilizing vertex cover algorithm that achieves (2–1 Δ)-approximation ratio, where Δ is the maximum degree of a given network. We first introduce a sequential (2–1 Δ)-approximation algorithm that uses a maximal matching with the high-degree-first order of vertices. Then we present a self-stabilizing algorithm based on the same idea, and show that the output of the algorithm is the same as that of the sequential one. We motivate and describe a new parameterized approximation paradigm which studies the interaction between performance ratio and running time for any parametrization of a given optimization problem. As a key tool, we introduce the concept of α-shrinking transformation, for α≥1. Applying such transformation to a parameterized problem instance decreases the parameter value, while preserving approximation ratio of α (or α-fidelity). For example, it is well-known that Vertex Cover cannot be approximated within any constant factor better than 2 [24] (under usual assumptions). Our parameterized α-approximation algorithm for k-Vertex Cover, parameterized by the solution size, has a running time of 1.273(2−α)k, where the running time of the best FPT algorithm is 1.273k [10]. Our algorithms define a continuous tradeoff between running times and approximation ratios, allowing practitioners to appropriately allocate computational resources. Moving even beyond the performance ratio, we call for a new type of approximative kernelization race. Our α-shrinking transformations can be used to obtain kernels which are smaller than the best known for a given problem. For the Vertex Cover problem we obtain a kernel size of 2(2−α)k. The smaller "α-fidelity" kernels allow us to solve exactly problem instances more efficiently, while obtaining an approximate solution for the original instance. We show that such transformations exist for several fundamental problems, including Vertex Cover, d-Hitting Set, Connected Vertex Cover and Steiner Tree. We note that most of our algorithms are easy to implement and are therefore practical in use. We give a nearly optimal sublinear-time algorithm for approximating the size of a minimum vertex cover in a graph G. The algorithm may query the degree deg(v) of any vertex v of its choice, and for each 1 ≤ i ≤ deg(v), it may ask for the ith neighbor of v. Letting VCopt(G) denote the minimum size of vertex cover in G, the algorithm outputs, with high constant success probability, an estimate [EQUATION] such that [EQUATION], where e is a given additive approximation parameter. We refer to such an estimate as a (2, e)-estimate. The query complexity and running time of the algorithm are O([EQUATION] · poly(1 e)), where d denotes the average vertex degree in the graph. The best previously known sublinear algorithm, of (STOC 2009), has query complexity and running time O(d4 e2), where d is the maximum degree in the graph. Given the lower bound of Ω(d) (for constant e) for obtaining such an estimate (with any constant multiplicative factor) due to Parnas and Ron (TCS 2007), our result is nearly optimal. In the case that the graph is dense, that is, the number of edges is Θ(n2), we consider another model, in which the algorithm may ask, for any pair of vertices u and v, whether there is an edge between u and v. We show how to adapt the algorithm that uses neighbor queries to this model and obtain an algorithm that outputs a (2, e)-estimate of the size of a minimum vertex cover whose query complexity and running time are O(n) · poly(1 e).