Multipass Streaming Algorithms for Regularized Submodular Maximization

Qinqin Gong ¹Suixiang Gao ²Fengmin Wang ³Ruiqi Yang¹

扫码查看

作者信息

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. Beijing Jinghang Research Institute of Computing and Communication,Beijing 100074,China
折叠

Abstract

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.

Key words

submodular optimization/regularized model/streaming algorithms/threshold

引用本文复制引用

基金项目

Beijing Natural Science Foundation Project(Z220004)

National Natural Science Foundation of China(11901544)

National Natural Science Foundation of China(12101587)

China Postdoctoral Science Foundation(2022M720329)

出版年

2024

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

清华大学

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

CSTPCDEI

影响因子：0.474

ISSN：1007-0214

参考文献量42

段落导航