# Metadata

- Title: Cardinality constrained submodular maximization for random streams
- Authors: Paul Liu, Aviad Rubinstein, Jan Vondrak, Junyao Zhao
- Year: 2021
- Venue: arXiv preprint (`arXiv:2111.07217v1`, November 13, 2021)
- Primary group: submodular
- Secondary tags: streaming, random-order, cardinality, non-monotone, hardness, secretary-shortlists
- Problem: cardinality-constrained monotone and non-monotone submodular maximization in the single-pass random-order streaming model
- Main guarantee: gives a simple `(1 - 1 / e - eps)` monotone algorithm and a `(1 / e - eps)` non-monotone algorithm using `O(k / eps)` memory, plus a hardness barrier of `1 - 1 / e + eps` for monotone random-order single-pass streaming
- Key techniques: random-window partitioning, pool reintroduction, shortlist-compatible buffering, greedy-style recurrences under random order, and hidden-good-element hardness gadgets
- Status: processed-deep, venue-year-to-verify
- Tags: #submodular #streaming #random-order #cardinality #non-monotone #hardness #approximation #arXiv
- Inbox source: inbox/2111.07217v1.pdf