An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

• 成果类型: Article; Early Access
• 署名作者: Alaluf, Naor; Ene, Alina; Feldman, Moran; Nguyen, Huy L.; Suh, Andrew
• 署名单位: Open University Israel; Boston University; University of Haifa; Northeastern University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1224
• 发表日期: 2022
• 关键词: approximations

摘要

We study the problem of maximizing a nonmonotone submodular function subject to a cardinality constraint in the streaming model. Our main contribution is a singlepass (semi) streaming algorithm that uses roughly O(k/epsilon(2)) memory, where k is the size constraint. At the end of the stream, our algorithm postprocesses its data structure using any off-line algorithm for submodular maximization and obtains a solution whose approximation guarantee is alpha/(1 + alpha) - epsilon, where a is the approximation of the off-line algorithm. If we use an exact (exponential time) postprocessing algorithm, this leads to 1/2 - epsilon approximation (which is nearly optimal). If we postprocess with the state-of-the-art offline approximation algorithm, whose guarantee is alpha = 0.385, we obtain a 0.2779-approximation in polynomial time, improving over the previously best polynomial-time approximation of 0.1715. It is also worth mentioning that our algorithm is combinatorial and deterministic, which is rare for an algorithm for nonmonotone submodular maximization, and enjoys a fast update time of O(epsilon(-2) (logk + log(1 + alpha))) per element.