In this work, we consider algorithms that process elements arriving in a random order. Note that the classical greedy algorithm which iteratively adds the best element [1]} cannot be used here, and hence we must look for new algorithmic techniques.
The motivation for considering random element arrival comes from the prevalence of submodularity in big-data applications, in which data is often logged in batches that can be modelled as random samples from an underlying distribution.Note that the random order assumption generalizes the typical assumption of i.i.d. sampling stream elements from a known distribution, as the random order assumption applies equally well to unknown distributions. The problem of streaming submodular maximization has recently received significant attention both for random arrival order and the more pessimistic worst-case order arrival [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}, [13]}, [14]}, [15]}, [16]}.
