333222170ab9edca4785c39f55221fe7-Paper.pdf

We consider the problem of maximizing submodular functions in single-pass streaming and secretaries-with-shortlists models, both with random arrival order. For cardinality constrained monotone functions, Agrawal, Shadravan, and Stein [ASS19]gaveasingle-pass(1 1/e ε)-approximation algorithm using only linear memory,buttheir exponential dependence onεmakesitimpractical evenforε = 0.1.