首页|Multipass Streaming Algorithms for Regularized Submodular Maximization

Multipass Streaming Algorithms for Regularized Submodular Maximization

扫码查看
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.

submodular optimizationregularized modelstreaming algorithmsthreshold

Qinqin Gong、Suixiang Gao、Fengmin Wang、Ruiqi Yang

展开 >

Beijing Institute for Scientific and Engineering Computing,Beijing University of Technology,Beijing 100124,China

School of Mathematical Sciences,University of Chinese Academy Sciences,Beijing 100049,China

Beijing Jinghang Research Institute of Computing and Communication,Beijing 100074,China

Beijing Natural Science Foundation ProjectNational Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaChina Postdoctoral Science Foundation

Z22000411901544121015872022M720329

2024

清华大学学报自然科学版(英文版)
清华大学

清华大学学报自然科学版(英文版)

CSTPCDEI
影响因子:0.474
ISSN:1007-0214
年,卷(期):2024.29(1)
  • 42