Approximation Algorithms For Facility Location And K-Median Problem With Differential Privacy

Given a facility set and a customer set in a metric space,and an opening cost for each facility,the facility location problem requires that some facilities are opened in the facility set and each customer is connected to an open facility,so as to minimize the sum of all facility opening costs and customer connection costs.In the k-median problem,there is no opening cost for each facility,but the number of opening facilities cannot exceed k.Its objective function is to minimize the sum of connection costs for all customers.Facility location problem and k-median problem are two important unsupervised learning problems in machine learning,and their theories and methods are widely used in biology,finance,natural language processing,automobile,aerospace manufacturing and other fields.In recent years,the problem of facility location problem k-median have been widely concerned.But with the continuous improvement of technology,people pay more and more attention to privacy issues.Among the existing privacy protection methods,differential privacy is a privacy protection framework that does not depend on the background knowledge of attackers and can quantify the degree of privacy protection.This paper mainly studies facility location problem and k-median problem with differential privacy approximation algorithms.These two problems require the algorithm to optimize the objective function of the facility location problem and the k-median problem under the condition of satisfying the definition of differential privacy.This paper studies the location of facilities with differential privacy in metric space.The algorithm mainly adopts the local search one-for-one technology.Firstly,the algorithm randomly selects a solution in the space,and then after T iterations,each time selects a solution from the adjacent solution space of the current solution with a certain probability as the current solution of the next iteration.In order to ensure the differential privacy,the exponential mechanism of the differential privacy is adopted in the iterative process,and the clustering cost is selected as the scoring function.Compared with the previous results,the approximate algorithm proposed in this paper has a constant multiplicative error of 4 and an additive error of O(Δn2lognlog(n+f/Δ)/ε).In this paper,the k-median problem with differential privacy in metric spaces is studied.Every step of the approximate algorithm for kmedian problem with differential privacy needs to add noise with a certain probability,so that the algorithm meets the definition of differential privacy.In this paper,the multi-exchange of local search technology is used to solve the k-median problem,and exponential mechanism is used to make the algorithm provide ε-differential privacy protection.In this paper,a set of facility swapping and customer allocation methods are designed to prove that the multiplicative error of the approximate algorithm is(4+2/p),and the additive error is O(Δ(4+2/p)2k2(p+1)log2n/ε),where p is the number of facility points that can be swapped at most in each exchange,n is the number of customers in the space,andΔ is the diameter of the metric space.When p≥2,the algorithm results reduce the multiplication error from 6 to(4+2/p)with almost the same additive error.