Indexed by:
Abstract:
In the paper, we design a privacy algorithm for maximizing a general submodular set function over a down-monotone family of subsets, which includes some typical and important constraints such as matroid and knapsack constraints. The technique is inspired by the measured continuous greedy (MCG) which compensates for the difference between the residual increase of elements at a given point and the gradient of it by distorting the original direction with a multiplicative factor. It directly makes the continuous greedy approach fit to the problem of maximizing a non-monotone submodular function. We generate the MCG algorithm in the framework of differential privacy. It is accepted as a robust mathematical guarantee and can provide the protection to sensitive and personal data. We propose a 1/e-approximation algorithm for the general submodular function. Moreover, for monotone submodular objective functions, our algorithm achieves an approximation ratio that depends on the density of the polytope defined by the problem at hand, which is always at least as good as the previously known best approximation ratio of 1 - 1 / e. © 2021, Springer Nature Switzerland AG.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2021
Volume: 13153 LNCS
Page: 212-226
Language: English
Cited Count:
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 7
Affiliated Colleges: