Our algorithm for non-monotone submodular functions is similar, with the caveat that here we also have to be careful about not including any element in the solution with large probability. This is an important aspect of the randomized greedy algorithm for (offline) non-monotone submodular maximization [1]} which randomly includes in each step one of the top \(k\)  elements in terms of marginal values. We achieve a similar property by choosing the top element from the current window and a random subset of the pool of prior elements \(H\) .
