Multipass Streaming Algorithms for Regularized Submodular Maximization

doi:10.26599/TST.2023.9010026

Multipass Streaming Algorithms for Regularized Submodular Maximization

2024-02-01

0

OA

AI

DOI：10.26599/TST.2023.9010026

Original

Original request for help

Save

Abstract

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.

Keywords:

Approximation algorithms

Linear programming

Boosting

submodular optimization

regularized model

streaming algorithms

threshold

Multipass Streaming Algorithms for Regularized Submodular Maximization

Abstract

Journal

Organization