Regularized two-stage submodular maximization under streaming  

作　　者：Ruiqi YANG Dachuan XU Longkun GUO Dongmei ZHANG 

机构地区：[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 Computer Science and Technology,Qilu University of Technology,Jinan 250353,China [4]School of Computer Science and Technology,Shandong Jianzhu University,Jinan 250101,China

出　　处：《Science China(Information Sciences)》2022年第4期98-107,共10页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant No.12101587);China Postdoctoral Science Foundation(Grant No.2021M703167);Fundamental Research Funds for the Central Universities(Grant No.EIE40108X2);supported by National Natural Science Foundation of China(Grant No.12131003);Beijing Natural Science Foundation Project(Grant No.Z200002);Longkun GUO was supported by National Natural Science Foundation of China(Grant No.61772005);Outstanding Youth Innovation Team Project for Universities of Shandong Province(Grant No.2020KJN008);Dongmei ZHANG was supported by National Natural Science Foundation of China(Grant No.11871081).

摘　　要：In the problem of maximizing regularized two-stage submodular functions in streams,we assemble a family F of m functions each of which is submodular and is visited in a streaming style that an element is visited for only once.The aim is to choose a subset S of size at mostℓfrom the element stream V,so as to maximize the average maximum value of these functions restricted on S with a regularized modular term.The problem can be formally casted as maxS⊆V,|S|≤ℓ 1/m ∑_(i=1)^(m) maxT⊆S,|T|≤k[f_(i)(T)−c(T)],where c:V→R+is a non-negative modular function and f_(i):2V→R+,∀i∈{1,...,m}is a non-negative monotone non-decreasing submodular function.The well-studied regularized problem of maxS⊆V,|S|6k f(S)−c(S)is exactly a special case of the above regularized two-stage submodular maximization by setting m=1 andℓ=k.Although f(·)−c(·)is submodular,it is potentially negative and non-monotone and admits no constant multiplicative factor approximation.Therefore,we adopt a slightly weaker notion of approximation which constructs S such that f(S)−c(S)>ρ·f(O)−c(O)holds against optimum solution O for someρ∈(0,1).Eventually,we devise a streaming algorithm by employing the distorted threshold technique,achieving a weaker approximation ratio withρ=0.2996 for the discussed regularized two-stage model.

关 键 词：submodular maximization streaming model TWO-STAGE threshold technique approximation algorithms 

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