Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

Understand

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem.

• However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature.
• In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat $1-\frac{1}{e}$ in the single-pass streaming model.
• Let $n$ be the number of elements in the stream.