RT Journal Article
A1 Qinqin Gong,Suixiang Gao,Fengmin Wang,Ruiqi Yang;
AD 科学与工程计算研究所, 中国 ; 数学科学学院, 中国 ; 北京京航计算与通信研究院, 中国 ; 科学与工程计算研究所, 中国
T1 Multipass Streaming Algorithms for Regularized Submodular Maximization
YR 2024
IS 1
vo 29
OP 76-OP 85
K1 threshold;submodular optimization;streaming algorithms;regularized model
AB In this work, we study a k-Cardinality Constrained Regularized Submodular Maximization ( k-CCRSM) problem, in which the objective utility is expressed as the difference between a non-negative submodular and a modular function. No multiplicative approximation algorithm exists for the regularized model, and most works have focused on designing weak approximation algorithms for this problem. In this study, we consider the k-CCRSM problem in a streaming fashion, wherein the elements are assumed to be visited individually and cannot be entirely stored in memory. We propose two multipass streaming algorithms with theoretical guarantees for the above problem, wherein submodular terms are monotonic and nonmonotonic.
SN 1007-0214
LA EN