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

Author:

Yang, Ruiqi (Yang, Ruiqi.) | Gao, Suixiang (Gao, Suixiang.) | Han, Lu (Han, Lu.) | Li, Gaidi (Li, Gaidi.) | Zhao, Zhongrui (Zhao, Zhongrui.)

Indexed by:

CPCI-S EI Scopus

Abstract:

We study a problem of maximizing the sum of a suBmodular and suPermodular (BP) function, denoted as max(S subset of V), (vertical bar S vertical bar <= k) g(S) + L(S), where g(.) is non-negative monotonic and submodular, L(.) is monotonic and supermodular. In this paper, we consider the K-cardinality constrained BP maximization under a streaming setting. Denote kappa as the supermodular curvature of L. Utilizing a distorted threshold-based technique, we present a first (1 - kappa)/(2 - kappa)-approximation semi-streaming algorithm and then implement it by lazily guessing the optimum threshold and yield a one pass, O(epsilon(-1) log ((2 - kappa)K/ (1 - kappa)(2))) memory complexity, ((1 - kappa)/(2 - kappa) - O(epsilon))-approximation. We further study the BP maximization with fairness constrains and develop a distorted greedy-based algorithm, which gets a (1 - kappa)/(2 - kappa)-approximation for the extended fair BP maximization.

Keyword:

Stream model Approximation algorithms Distorted threshold Submodular maximization Fairness

Author Community:

  • [ 1 ] [Yang, Ruiqi]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 2 ] [Gao, Suixiang]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 3 ] [Han, Lu]Beijing Univ Posts & Telecommun, Sch Sci, Beijing 100876, Peoples R China
  • [ 4 ] [Li, Gaidi]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 5 ] [Zhao, Zhongrui]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Related Article:

Source :

PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PDCAT 2021

ISSN: 0302-9743

Year: 2022

Volume: 13148

Page: 452-459

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 9

Affiliated Colleges:

Online/Total:747/10646117
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.