.png){kind=icon}
返回
Multipass Streaming Algorithms for Regularized Submodular Maximization
.png){kind=icon}
OA
AI
DOI：10.26599/TST.2023.9010026.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Approximation algorithms
Linear programming
Boosting
submodular optimization
regularized model
streaming algorithms
threshold
期刊
T
IF:
3.5
论文数:
987
被引数:
2.5K
机构
引用论文
Sequencing of the Complete Mitochondrial Genome of Pingus sinensis (Spirurina: Quimperiidae): Gene Arrangements and Phylogenetic Implications.png)
GenesOAAI
GenesIF0
OAAI分享收藏
查看更多内容