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

Chien-Chung Huang, Naonori Kakimura, Simon Mauras +1

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…