Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity

Abstract

Streaming algorithms are generally judged by the quality of their solution, memory footprint, and computational complexity. In this paper, we study the problem of maximizing a monotone submodular function in the streaming setting with a cardinality constraint $k$. We first propose Sieve-Streaming++, which requires just one pass over the data, keeps only $O(k)$ elements and achieves the tight $(1/2)$-approximation guarantee. The best previously known streaming algorithms either achieve a suboptimal $(1/4)$-approximation with $\Theta (k)$ memory or the optimal $(1/2)$-approximation with $O(k\log k)$ memory. Next, we show that by buffering a small fraction of the stream and applying a careful filtering procedure, one can heavily reduce the number of adaptive computational rounds, thus substantially lowering the computational complexity of Sieve-Streaming++. We then generalize our results to the more challenging multi-source streaming setting. We show how one can achieve the tight $(1/2)$-approximation guarantee with $O(k)$ shared memory while minimizing not only the required rounds of computations but also the total number of communicated bits. Finally, we demonstrate the efficiency of our algorithms on real-world data summarization tasks for multi-source streams of tweets and of YouTube videos.

Proceedings of the 36th International Conference on Machine Learning, Long Beach, California, PMLR 97, 2019

References in corpus (3)

• Beyond $1/2$-Approximation for Submodular Maximization on Massive Data Streams
• Non-monotone Submodular Maximization in Exponentially Fewer Iterations
• Unconstrained Submodular Maximization with Constant Adaptive Complexity

Cited by in corpus (13)

• The FAST Algorithm for Submodular Maximization
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
• Improved Submodular Secretary Problem with Shortlists
• Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models
• Cardinality constrained submodular maximization for random streams
• Dynamic Influence Maximization
• FPT-Algorithms for the \ell-Matchoid Problem with a Coverage Objective
• Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
• A polynomial lower bound on adaptive complexity of submodular maximization
• Submodular Matroid Secretary Problem with Shortlists
• GPU-Accelerated Optimizer-Aware Evaluation of Submodular Exemplar Clustering
• Fast Parallel Algorithms for Submodular $p$-Superseparable Maximization