Indexed by:
Abstract:
We consider the problem of local privacy where actions are subsets of a ground multiset and expectation rewards are modeled by a 1-decomposable monotone submodular function. For the DR-submodular maximization problem under a polymatroid constraint, Soma and Yoshida [26] provide a continuous greedy algorithm for no-privacy setting. In this paper, we obtain the first differentially private algorithm for DR-submodular maximization subject to a polymatroid constraint. Our algorithm achieves a (1 - 1/e - O(rho))-approximation with a little loss and runs in O(n(2)r(3)/rho(6) .log(3)(n/rho).log(3)r + n(8)) times where r is the rank of the base polymatroid and n is the size of ground set. Along the way, we analyze the utility and privacy of our algorithm. A concrete experiment to simulate the privacy Uber pickups location problem is provided, and our algorithm performs well within the agreed range.
Keyword:
Reprint Author's Address:
Email:
Source :
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
ISSN: 0129-0541
Year: 2023
0 . 8 0 0
JCR@2022
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:19
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 19
Affiliated Colleges: