• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Sun, Xin (Sun, Xin.) | Li, Gaidi (Li, Gaidi.) | Zhang, Yapu (Zhang, Yapu.) | Zhang, Zhenning (Zhang, Zhenning.)

Indexed by:

EI Scopus

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:

Approximation algorithms Combinatorial optimization Sensitive data

Author Community:

  • [ 1 ] [Sun, Xin]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 2 ] [Li, Gaidi]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 3 ] [Zhang, Yapu]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 4 ] [Zhang, Zhenning]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2021

Volume: 13153 LNCS

Page: 212-226

Language: English

Cited Count:

WoS CC 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:

Online/Total:762/10658009
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.