RT Journal Article
A1 Ruiqi Yang,Suixiang Gao,Lu Han,Gaidi Li,Zhongrui Zhao;
AD 科学与工程计算研究所, 中国 ; 数学科学学院, 中国 ; 理学院, 中国 ; 科学与工程计算研究所, 中国 ; 科学与工程计算研究所, 中国
T1 Approximating (mB,mP)-Monotone BP Maximization and Extensions
YR 2023
IS 5
vo 28
OP 906-OP 915
K1 approximation algorithm;submodular maximization;streaming model;threshold technique
AB The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a ((1-κ)/(2-κ)-𝒪(ε))-approximation with 𝒪(1/ε4log3(1/ε)log((2-κ)k/(1-κ)2)) memory complexity, where κ denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a ((1-κ)4/(2-2κ+κ2)2-𝒪(ε))-approximation algorithm.
SN 1007-0214
LA EN