Cardinality constrained submodular maximization for random streams

Paul Liu, Aviad Rubinstein, Jan Vondrak +1

We consider the problem of maximizing submodular functions in single-pass streaming and secretaries-with-shortlists models, both with random arrival order. For cardinality constrai…