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

Author:

Hu, Jiaming (Hu, Jiaming.) | Hao, Chunlin (Hao, Chunlin.) | Miao, Cuixia (Miao, Cuixia.) | Zhao, Bo (Zhao, Bo.)

Indexed by:

Scopus SCIE

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:

polymatroid constraint differentially private Submodular maximization

Author Community:

  • [ 1 ] [Hu, Jiaming]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Hao, Chunlin]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Zhao, Bo]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 4 ] [Miao, Cuixia]Qufu Normal Univ, Qufu 273165, Peoples R China

Reprint Author's Address:

  • [Miao, Cuixia]Qufu Normal Univ, Qufu 273165, Peoples R China;;

Show more details

Related Keywords:

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:

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

Online/Total:690/10645643
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.