Approximating(mB,mP)-Monotone BP Maximization and Extensions  

作　　者：Ruiqi Yang Suixiang Gao Lu Han Gaidi Li Zhongrui Zhao 

机构地区：[1]Beijing Institute for Scientific and Engineering Computing,Beijing University of Technology,Beijing 100124,China [2]School of Mathematical Sciences,University of Chinese Academy Sciences,Beijing 100049,China [3]School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China

出　　处：《Tsinghua Science and Technology》2023年第5期906-915,共10页清华大学学报（自然科学版（英文版）

基　　金：supported by the National Natural Science Foundation of China(No.12101587);the China Postdoctoral Science Foundation(No.2022M720329);the National Natural Science Foundation of China(No.12001523);the Beijing Natural Science Foundation Project(No.Z200002);the National Natural Science Foundation of China(No.12131003).

摘　　要：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-k)/(2-k)-O(e)-approximation with O(1/e^(4)1og^(3)(1/s)log(2-k)k/(1-k)^(2))memory complexity,where k 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-k)^(4)/(2-2k+k^(2))^(2)-O(e)-approximation algorithm.

关 键 词：submodular maximization streaming model threshold technique approximation algorithm 

分 类 号：O17[理学—数学]