• 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 SCIE

Abstract:

We propose a private algorithm for the problem of maximizing a submodular but not necessary monotone set function over a down-closed family of sets. The constraint is very general since it includes some important and typical constraints such as knapsack and matroid constraints. Our algorithm DIFFERENTIALLY PRIVATE MEASURE Corm.iuous GREEDY is proved to be O(epsilon)-differential private. For the multilinear relaxation of the above problem, it yields (T e(-T)- o(1))-approximation guarantee with additive error O (2 Delta/epsilon n4), where T is an element of [0, 1] is the stopping time of the algorithm, A is the defined sensitivity of the objective function, which is associated to a sensitive dataset, and n is the size of the given ground set. For a specific matroid constraint, we could obtain a discrete solution with near 1/e-approximation guarantee and same additive error by lossless rounding technique. Besides, our algorithm can be also applied in monotone case. The approximation guarantee is (1 - e(-T)- 0(1)) when the submodular set function is monotone. Furthermore, we give a conclusion in terms of the density of the relaxation constraint, which is always at least as good as the tight bound (1 - 1/e).

Keyword:

Differential privacy Measured continuous greedy Down-closed family of sets Approximation algorithm Submodular maximization

Author Community:

  • [ 1 ] [Sun, Xin]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Li, Gaidi]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Zhang, Yapu]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 4 ] [Zhang, Zhenning]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

Year: 2022

Issue: 5

Volume: 44

Page: 3212-3232

1 . 0

JCR@2022

1 . 0 0 0

JCR@2022

ESI Discipline: MATHEMATICS;

ESI HC Threshold:20

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 36

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 13

Affiliated Colleges:

Online/Total:557/10637217
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.