Indexed by:
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:
Reprint Author's Address:
Email:
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: