Cardinality constrained submodular maximization for random streams
Authors: Paul Liu
Aviad Rubinstein
Jan Vondrak
Junyao Zhao
Venue: NeurIPS 2021 Poster (2021)
Keywords: submodular
streaming model
optimization
cardinality constraint
approximation algorithms

Abstract: 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~\cite{SMC19} gave a single-pass $(1-1/e-\varepsilon)$-approximation algorithm using only linear memory, but their exponential dependence on $\varepsilon$ makes it impractical even for $\varepsilon=0.1$.
We simplify both the algorithm and the analysis, obtaining an exponential improvement in the $\varepsilon$-dependence (in particular, $O(k/\varepsilon)$ memory).
Extending these techniques, we also give a simple $(1/e-\varepsilon)$-approximation for non-monotone functions in $O(k/\varepsilon)$ memory. For the monotone case, we also give a corresponding unconditional hardness barrier of $1-1/e+\varepsilon$ for single-pass algorithms in randomly ordered streams, even assuming unlimited computation. 

Finally, we show that the algorithms are simple to implement and work well on real world datasets.

Cardinality constrained submodular maximization for random streams
Paul Liu
Aviad Rubinstein
Department of Computer Science
Department of Computer Science
Stanford University
Stanford University
paul. liu@stanford. edu
aviad@stanf ord. edu
Jan Vondrák
Junyao Zhao Department of Computer Science
Department Mathematics
Stanford University grondrak@stanffoo edu
Stanford University junyaoz0stanford edu
Abstract
We consider the problem of maximizing submodular functions in single-pass streaming and secretaries- siietiiss-wi---hootiitt models, both with random arrival or- der. For cardinality constrained monotone functions, Agrawal, Shadravan, and Stein [ASS19] gave single-pass (1 1/c apprroxxmmmtio algorithm using only linear memory, but their exponential dependence on makes it impractical even for 0.1. We simplify both the algorithm and the analysis, obtaining an exponential improvement in the e-dependence (in particular, O(k/e) memory). Extending these techniques, we also give a simple (1/e - e) -apppoximmaioon for non-monotone functions in O(k/e) memory. For the monotone case, we also give a corresponding unconditional hardness barrier of 1/e + for single-pass algorithms in randomly ordered streams, even assuming unlimited computation.
Finally, show that the algorithms are simple to implement and work well on real world datasets.
Introduction
Over the past few decades, submodularity has become recognized useful property occurring in a wide variety of discrete optimization problems. Submodular functions model the property of diminishing returns, whereby the gain in a utility function decreases the of items considered increases. This property occurs naturally in machine learning, information retrieval, and influence maximization, to name few (see [IKBA20] and the references within).
In many settings, the data is not available in a random-access access model; either for external reasons (customers arriving online) or because of the massive amount of data. When the data becomes too big to store in memory, we look for streaming algorithms that pass (once) through the data, and efficiently decide for each element whether discard it keep it in small buffer in memory.
In this work, we consider algorithms that process elements arriving the classical greedy algorithm which iteratively adds the best element [NWF78] 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 often logged in batches that can be modelled as random samples from an underlying
random order. Note that
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

distribution. The problem of streaming submodular maximization has recently received significant attention both for random arrival order and the more pessimistic worst-case order arrival [ASS19, AEF+ 20, AF19, BMKK14, BV14, CGQ15, FKK18, FNS720, HKMY20, IV19, KMZ* 19, MV19, N8M+ HTW20, Sha20].
1.1 Submodular functions and the streaming model
Let f 2 + R4 be non non-negative set function satisfying ((SU())))f(()) 2 f(TUfe))- for all S C CE E\ fe]. Such function is called submodular. For simplicity, we assume f(0) 0. We use the shorthand [(e]S)= == S(S {e}) ((S) to denote the marginal of e on top of S. When f(S) < ((T) for all _ f called monotone. We consider the following optimization problem:
OPT
max (S)
S
where k is cardinality constraint for the solution size.
Our focus on submodular maximization in the streaming setting. In this setting, an algorithm is given single pass over dataset in a streaming fashion, where the stream is a some permutation of the input dataset and each element seen once. The stream is in random order when the permutation is uniformly random. When there no constraints the stream order, call the stream adversarial.
At each step of the stream, our algorithm is allowed maintain buffer of input elements. When a new element is streamed in, the algorithm can choose to add the element to its buffer. To be as general as possible, we assume an oracle model that is, we assume there an oracle that returns the value of f(S) for any set S. The decision of the algorithm to add an element is based only on queries to the oracle on subsets of the buffer elements. The algorithm may also choose to throw away buffered elements at any given time. The goal in the streaming model is to minimize memory use, and the complexity of the algorithm the maximum number of input elements the algorithm stores in the buffer at any given time.
For the oracle model, an important distinction is between weak oracle access or and strong oracle access. In the weak oracle setting, the algorithm is only allowed to query sets of feasible elements (sets that have cardinality less than k). In the strong oracle setting however. the algorithm allowed to query any set of elements. All our results apply to both the weak and strong oracle models.
Our aim will be to develop algorithms that only make one pass over the data stream, using (k) memory, where k is the maximum size of solution set in I. We assume that & is small relative to n : E), the size of the ground set.
1.2 Our contributions
On the algorithmic side, we give (1-1/e-e) and (1/c-E) approximation for cardinality constrained monotone and non-monotone submodular maximization respectively. both using Okk/E) memory. The monotone result has an exponential improvement in memory requirements compared Agrawal et al. [ASS19] (in terms of the dependence on e), while the non-monotone result is the first to appear in the random-order streaming model, and improves upon the best known polynomial- time approximations under adversarial orders (AF++200. The algorithms are extremely simple to implement, and perform well on real world data (see Section 5), even compared offline greedy algorithms.
On the hardness side, prove that (1 - 1/e + >>approxxmmttinn for monotone submodular maximization would require 2(n) memory (even with unlimited queries and computational power). This improves the hardness bound of 7/8 from [ASS19].
1.3
Related work
Prior work on this problem has focused on both the adversarial and random-order streaming setting. Algorithmic and hardness results further depend whether the function f is monotone non-
NNoe that random order assumption generalizes the typical assumption i..d sampling stream elements from known distribution, as the random order assumption applies equally well to unknown distributions. Submodular functions f with f(0) > 0 only improves the approximation ratio of algorithms.

---

adversarial order
random order
2 1/2 - (O(k/E) [KMZ* 19I)
1/2 + c, C < 10 (O log k) INTM 18))
1 - 1/e- - s (O exp(poly(11ppslm [ASS19])
$ 11/2+ (W+S [NTM*18 18, FNS7200)
monotone
1 1/e+ (S)
I 22/(2 v22 (S [HKMY20J)
1/e- (O(k/e), this paper)
2 21/2 -E (unbounded comp,
((k/E²) [AEF**2]]
0.2779 (O(k) [AEF+20])
1/e (O(k/e). this paper)
non-mono.
0.1715 (O(k) [FKK18])
1/2 (W [AEF* 20))
Table 1: A survey of results on monotone submodular streaming. Our contributions are highlighted in magenta. W weak oracle, S strong oracle, complexities refer memory use. Lower-bounds propagate downwards in the table. Note that our polynomial- time algorithms require only weak oracle access, while our hardness results hold even for strong oracle.
monotone, and whether f has explicit structure (e.g. such as by presenting a set system for in the coverage case), or accessible only via oracle queries. Table describes all the relevant results.
Algorithmic results. Submodular maximization in the streaming setting was first considered by Badanidiyuru et al. [BMKK14] who gave a (1/2 - -pprroxiimttoonnn in O log k/e) memory for monotone submodular functions under cardinality constraint, using thresholding idea with parallel enumeration of possible thresholds. This work led to a number of subsequent developments with the current best being (1/2- j--apprxximation in (k//c) memory [KMZ+ 19]. It turns out that the factor of //2rx is the best possible in the adversarial setting (with a weak oracle), but an improvement possible in the random order model (the input is ordered by uniformly random permutation). This was first shown by Norouzi-Fard et al. [NTM+ 18), who proved that the 1/2 1/2-hardness barrier for cardinality constraints can be broken, exhibiting a (1/2 + -)parooxiittoo in (k// log k) memory where < 10-13 In a breakthrough work, Agrawal, Shadravan. and Stein [ASS19] gave a (1 - 1/e - a)aaproxximttion using k 2poly(1/s) memory and running time. We note that this is arbitrarily close to the optimal factor of 1/c, but the algorithm is not practical, due to its dependence on e (even for e 0.1, the resulting constants are astronomical).
Lower bounds. A few lower bounds are known for monotone functions in the adversarial order model: with a weak oracle, any (1/2- + e) -approximation would require Q(n/k) memory [NTM* 18]. Under strong oracle, lower bound of (2n k-3) memory for any (1/2 + + apprroxiimttoonnn algorithm was shown in a recent paper by Feldman et al. [FNSZ20]. Another recent lower bound was proved by McGregor and Vu 19V19]: (1 1/c + e) approoximttionn for coverage functions requires 22(n/ ( memory (this lower bound holds for explicitly given inputs, via communication complexity; we note that this is incomparable to the computational (1 1/c + -hardness of maximum coverage [Fei98]). For non-monotone functions, Alaluf et al. [AEF+ 20] proved an ②(n) memory lower bound for the adversarial order model with unbounded computation.
In the random-order model, Agrawal et al. [ASS19] show that beating 7/8 (for monotone submodular functions) requires ((n) memory. In contrast, show that same construction as McGregor and Vu [MV19] also applies to randomly ordered streams: - 11-1/e+ =) for coverage functions requires O(n ) memory even in the random-order model.
Submodular maximization in related models. closely related model is the secretary with shortlists model [ASS19], where an algorithm is allowed to store shortlist of more than k items (where l is the cardinality constraint). Unlike the streaming model however, once an element goes into the shortlist, it cannot be removed. Then, after seeing the entire stream, the algorithm chooses subset of size from the shortlist and returns that to the user. We note that the algorithms developed in this paper apply almost without modification to the shortlists model.
3

---

1.4 Overview of our techniques
Main algorithmic techniques. The primary impetus for our algorithmic work was an effort to avoid the extensive enumeration involved in the algorithm of Agrawal et al. [ASS19] which leads to memory requirements exponential in poly(1/E),
To make things concrete, let us consider the input divided into disjoint windows of consecutive elements. The windows containing actual optimal elements play special role -ile-llo let's call them active windows- - these are the windows where we make quantifiable progress. When the stream randomly ordered, we would ideally like to have each new element sampled independently and uniformly from the input. This leads to the intuition that the optimal elements are evenly spread out through all the windows. This cannot be literally true, since conditioned on the history of the stream, some elements have already appeared and cannot appear again. However, key idea of Agrawal et al. [ASS19] allows us to circumvent this by reinserting the elements that we have already seen and that played role in the selection process. What needs to be proved is that elements that were not selected can still appear in the future, conditioned on the history of the algorithm; that turns out to be true, provided that our algorithm operates in a certain greedy-like manner.
To ensure progress was made regardless of the positioning of the optimal elements, previous work made use of exponentially large enumerations to essentially guess which windows the optimal elements arrive in. Where we depart from previous work is the way we build our solution. The idea is to use an evolving family of solutions which are updated in parallel, so that we obtain a quantifiable gain regardless of where the optimal elements arrived. Specifically, we grow 1 solutions in parallel, where solution L; has cardinality i. In each window, we attempt to extend a collection of solutions L, (for varying i) by a new element e; if e beneficial on average to every L; in the collection, we replace each 1.+11 with the new solution L, U {e). Regardless of which windows happen to be active, we will show that the average gain over our evolving collection of solutions is analogous to the greedy algorithm. This is the basis of the analysis that leads to a factor of 1 - 1/e.
In addition our candidate solutions Li, we maintain a pool of elements Il that our algorithm has ever included in some candidate solution. We then use H to reintroduce elements artificially back into the input: this makes it possible assume that every input element still appears in a future window with the same probability, which is key to the probabilistic analysis leading to 1 - 1/c.
Non-monotonn functions. Our algorithm for non- moootoone 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 [BFNS14] 14] which randomly includes in each step one of the top & elements terms of marginal values. We achieve a similar property by choosing the top element from the current window and random subset of the pool of prior elements H.
Hardness results. Our hardness instances have the following general structure: there is a special subset of k good elements, and the remaining n A elements are bad. The good elements are indistinguishable from each other, and ditto for the bad elements. In the monotone case, any bad elements are (1 -fctor worse than the optimal solution (k good elements). Suppose furthermore that for parameter r > 0, as long as we never query the function on a subset with 2 r good elements, the good elements are indistinguishable from bad elements. The only way to collect 2 good elements in the memory buffer is by chance until we' ve collected the required number of good elements, they are indistinguishable from bad elements, so the subset in the memory buffer is random. The classic work of Nemhauser and Wolsey [NW78] constructs a pathological monotone submodular function with s(k),, which we use to prove that without memory 2(n) the algorithm cannot beat 1 - l/e.. McGregor and Vu [MV19] construct a simple example of a coverage function with r = 2, which we use for our Q(n/K) (k)k) bound. For an exponential-size ground set, we extend their construction to r = 3 which translates the improved lower bound of ((n/k3/2).
2 A (1
- (lle--e--pppee 1 approxxmmatio in O(k/E) memory
In this section, we develop a simple algorithm for optimizing a monotone submodular function with respect to a cardinality constraint. Due to space limitations, we focus on the intuition behind the results. Full proofs can be found in the supplementary.
4

---

key lemma Our algorithm begins by randomly partitioning the stream E into ak contiguous windows of expected size n((a)), where a is a parameter controlling the memory dependence and approximation ratio. This is done by generating random partition according to Algorithm 1. As the algorithm progresses, it maintains partial solutions, the ê-th of which contains exactly l elements. Within each window we process all the elements independently, and choose one candidate element to extend the partial solutions by. We then add e to a collection partial solutions Le at the end of the window. The range of partial solution sizes l that we use roughly tracks the number of optimal elements we are expected to have seen so far in the stream.
Intuitively, our algorithm is guaranteed to make progress on windows that contain an element from the optimal solution O. Let loosely call such windows active (a precise definition will be given later). Of course, the algorithm never knows which windows are active. However, the key idea of our analysis is that we are able to track the progress that our algorithm makes on active windows. Since the input stream is uniformly random, intuitively we expect to see i/a optimal elements after processing windows. With high probability, the true number of optimal elements seen will be in the range R = [i/a - Ö(VR), i/a + ((V)). By focusing on the average improvement over levels in R. we can show that each level f in this range gains & {f(O) f(Le-1)) in expectation, whenever (random) optimal element arrives.
For the analysis to work, ideally we would like each arriving optimal element to be selected uniformly among all optimal elements. This is not true conditioned on the history of decisions made by the algorithm. However, we can remedy this by re- re-inserting elements that we have selected before and subsampling the elements in the current window, with certain probabilities. (Lemma 2.2) shows why this works, since the elements we have never included might still appear, given the history of the algorithm. Our basic algorithm is described in Algorithm 2, with the window partitioning procedure described in Algorithm 1.
Algorithm Partitioning stream into m windows.
1: Draw E integers uniformly from 1,..., m
2: n; + # of integers equal to i
3: 4 Σisjet n4
4: for = 1,...., do
5:
W/ f- elements t, to t. + n4 in E
6: return [wi, W2..... W2...., wm)
Algorithm 2 MO
1: Partition E into windows w; for = I,..., ak with Algorithm 1.
2: L +- 0 for É = 0,
3: ++00
4: for i ak do
5:
C + wi
6:
Li + Li for l 10,,....ff
7:
Sample each H with probability at and add set R.
8:
C.+CURR C,U,R
9:
2, max [i/a| 20a /log kJ. minfk, [i/a] 20og/logh)
10:
ex + argmax,ec; Σt L(
11:
if
L== E f(L) - {E*1) Eie., f(1i7)) then
12:
H [e*
13:
L'41 t -i-l fet) for all e E [a, anl
-
for l
1,2..., do
15:
if ((L)) 2 ((L then
16:
1/ + D + arg max [(e(
return arg max max k(
In most basic implementation, Algorithm requires O(ak + k2) memory (to store H and T. for & 0,...,k) k). However, there several optimizations can make. Algorithm 2 can be
5

---

implemented in way that the Lÿ's are not directly stored at all. To avoid storing the L we can augment H to contain not just e", but also the index of the window was added in. The index of the window tells us the range of levels that e* was inserted into, so all of the T. s can be reconstructed from H as H contains history of all the insertions. Thus the memory use of Algorithm 2 is the size of H at the end of the stream. Since there are ork windows and each window introduces at most 1 element to H. we have the following observation:
Observation 2.1. Algorithm 2 uses at most O(ak) space and O(nay log k) time.
When E' is streamed in random order, our partitioning procedure (Algorithm 1) has a much simpler interpretation. (A similar lemma can be found in the appendix of Agrawal et al. [ASS19].)
Lemma 2.1. Suppose E is streamed according to a permutation chosen at random and we partition E by Algorithm/ I into m windows. This is equivalent to assigning each e. E to one of m different buckets uniformly and independently at random.
The algorithm's 's performance and behavior depends on the ordering of E. Let us define the history of the algorithm up to the i-th window, denoted H4, to be the sequence of all solutions produced up to that point. (Note that this history is only used in the analysis.) More precisely, we define the history as follows.
Definition 2.1. Let H; denote the state of the set H maintained by the algorithm, before processing window i. We define Hi to be the set of all triples (e, E.j) such that element H2 was added to solution Lg in window j. In other words, H4 contains all of the changes that the algorithm made to its state while processing the first i windows. For convenience, sometimes we treat H4 as set of elements and say that e E Hi ife E H;,
The history Hi describes the entire memory state of the algorithm up to the end of window i 1. In the following, we analyze the performance of the algorithm in the i-th window conditioned the history H4. Note that different random permutations of the input may produce this history, and we average over all of them the analysis.
The next key lemma captures the intuition that elements not selected by the algorithm so far could still appear in the future, and bounds the probability with which this happens.
Lemma 2.2. Fix a history H4-1. For any element e E E \ H4-1, and any i S i' S m = ak, we have Pr (e w H4-1) 2 1/(ak)).
Next, define set of active windows. In each active window, the algorithm is expected make significant improvements to its candidate solution. The active windows will only be used in the analysis of the algorithm, and need not be computed in any way.
Definition 2.2. Let O be the optimal solution. For window i, let y be the probability that e E w; given H4-1 Define its active set A, to be the union of R2 and the set obtained by sumpling each e E w, with probability 1/(akp'). We call wi an active window IfO n Arl 2 1 and we call O n A, the active optimal elements of window i.
Note that the construction of active sets in Definition 2.2 is valid Lemma 2.2 guarantees 1/(akp')) < 1. More importantly, the active window A, subsamples the optimal elements so that each element appears in A; with probability exactly 1 1/(ak) regardless of the history Hi-1. This allows us to tightly bound the number of active windows in the input, as we show in the next lemma.
Lemma 2.3. Suppose we have streamed up to the a,3-th window of the input for some 3 > 0. Then expected number of active windows seen so far satisfies
Zag == expected number of active windows = B O(3/a).
Furthermore, the actual number of windows concentrates around Zug to within +o (v
with probability 1 1 6.
Next we analyze the expected gain in the solution after processing each active window. Let Aiti the event that window w,-1 is active.
Lemma 2.4. Let C. = {zf, z + +,...,,,?, where 2f and 2i, are the values of 21 and zh defined in Algorithm 2 on window i. Conditioned on a history H, and window i + being active,
Σ E[f(Lit)) - f(L)) A+t1l REL
1 Σ (f(0) - EE)(() Hil)
(1)
EEC+t1

---

Under an ideal partition, each element of O appears in a different window, with one optimal element appearing roughly once every a windows. Thus after h active windows, we expect to obtain
1 (1 1/k)* ~ (1 (1-1) 1/e))aappoxxiiaaionn (as in the standard greedy analysis).
Theorem 2.5. The expected value of the best solution found by the algorithm is at least
(1-2-0 aav log k
) DOPT.
e
Setting a ((1/E), we have a (1 1/e- -E- aaprrxiaaiinnniaon using Okk/s) memory.
3 A -l/pe-aaapprooxinatio for non-monotone submodular maximization
In this section, we show that the basic algorithm described in Algorithm 2 can be altered to give 1/c //eaapprxximatin to the cardinality constrained non-monotone case (Algorithm 3).
Algorithm 3 NONNMONTTONISTREAMI...
1: Partition E into windows Wy for 1,..., ak with Algorithm 1.
2: Li +- 0 for i = .,...,k
3: +-40 -0
4: xt Unif(0, 1) for E, [ak]
5: for i = 1,...,ak al do
6:
C. 4
7:
for e E window w, do
8:
for j .,..., do Reconstruct T--- for all from Hi-1
9:
10:
A = fr /r/1srss Ei f(elLe < for or or > det (see line 13 for f.)
L ab-s+1121+1
11:
ak
if < de then C. + (ufe
13:
f - [(e [(e))
14:
Perform lines 7 to 16 of Algorithm 2.
15:
return arg max, f(L
Algorithm 3 uses the same kind of multi-level scheme as Algorithm 2. However, Algorithm further sub-samples the elements of the input that the probability of including any element is exactly 1/(ak) lines 7-13 (coloured in orange). The sub-sampling allows us to bound the maximum probability that element of the input is included in the solution. In particular, the sub-sampling is done by having the algorithm compute (on the fly) the conditional probability that an element e could have been selected had it appeared in the past. This gives us the ability to compute an appropriate sub-sampling probability to ensure that does not appear in H with too high probability. In terms of the proof, the sub-sam sampling allows us to perform similar analysis to the RANDOMGREEDY algorithm of Buchbinder et al. [BFNS14]]2
Since many of the main ideas the same, we relegate the details of the analysis the supplementary.
Implementation of Algorithm 3 For clarity of exposition, we compute or up front in line However, we can compute them on the fly in practice since each element only uses its value of x once (lines 10 and 12). This avoids an O(nak) memory cost associated with storing each x'. Finally, we assume that there are ties when computing the best candidiate element in each window. Ties can be handled by any arbitrary but consistent tie- breaking procedure. Any additional information used to break the ties (for example ordering on the elements e) must be stored alongside fa for the computation of A (line 10).
Theorem 3.1. Algorithm 3 obtains a (1/e approxxmmaai for maximizing non-monotone function f with respect to a cardinality constraint in O(k/e) memory.
A difference here is that instead of analysing a random element of the top-k marginals, we analyse the optimal set directly.

---

We remark that Algorithm 3 also achieves a guarantee of 1 1/e for the monotone case, as Lemma 2.4 and Theorem 2.5 both still apply to Algorithm when fis monotone. The main difference between the two is the sub-sampling (lines 7-13), which increases the running time of the algorithm.
4 1 - 1/e hardness for monotone submodular maximization
The proofs the following propositions and lemmas may found in the supplementary.
Proposition 4.1. Fix subsets G, of elements (denoting "good" and "bud") such that [G] = k and [B] = n. k; let r E [0, k] be some parameter. Let denote the size of the memory buffer, and let p denote the probability that a random subset of size m contains at least r good elements. Let f: GUUBB IR be function that satisfies the following symmetries:
f is symmetric good (resp. bad) elements, namely there exists f such that f(S) fGl Bl).
For any set with S 1r-1goom elements, f does not distinguish between good and bad elements, namely for ----1, b) f(0.b b g)-
Then any algorithm has expected value at most
ALG s 111-pha (00 + pk OPT.
We now consider a few different f's that satisfy the desiderata of Proposition 4.1.
Lemma 4.1 (monotone submodular function [NW78]). There exists monotone submodular f that satisfies the desiderata of Proposition 4. for 2ek, and such that:
f(0,k) - 1/e Oss).
OPT (G)
Lemma 4.2 (polynomial-univess, coverage function [MV19]). There exists (monotone submodular) coverage function f over a polynomial universe U that satisfies the desiderata of Proposition 4.1 for r and such that:
f(0, k) (1- 1/e 1//e+000 o(1))
ffC)=(C)=(()))
Lemma 4.3 (exponential-univers coverage function (new construction)). There exists (monotone submodular) coverage function J over an exponential universe U that satisfies the desiderata of Proposition 4.1 for = 3, and such that:
f(0,k) (1 1/e o(1))UU)
. OPT= = -U%.
Our main hardness result follows from the lemmas above:
Theorem 4.4. Any (1 - 1/e -aapppoxxmmatton algorithm in the random order strong oracle model
must use the following memory:
I(n) for a general monotone submodular function.
D(n/k' k2) for a coverage function over polynomial universe.
9(n/k3/2) k32)) for coverage function over an exponential universe.
5 Experimental results
In the following section, we give experimental results for our monotone streaming algorithm. Due to space limitations, the experiments for the non-monotone algorithm can be found in the supplementary.

---

Our main goal is to show that our algorithm performs well in practical setting and is simple to implement. In fact, we show that our algorithm on par with offline algorithms in performance, and returns competitive solutions across variety of datasets. All experiments were performed on a 2.7 GHz dual-core Intel i7 CPU with 16 GB of RAM.
We compare the approximation ratios obtained by our algorithm with three benchmarks:
The offline LAZYGREEDY algorithm [Min78], which is both theoretically optimal and obtains the same solution as greedy (in faster time). Note that we don't expect to outperform it with a streaming algorithm; but as we hoped, our algorithm comes close.
The SIEVESTREAMING algorithm of Badanidiyuru et al. [BMKK14] 14], which is the first algorithm to appear for adversarial streaming submodular optimization.
The SALSA algorithm of Norouzi-Fard et al. [NTM + 18], which is the first "beyond 1/2" approximation algorithm for random-order streams. This algorithm runs several varients SIEVESTREAMING in parallel with thresholds that change as the algorithm progresses through the stream. for adversarial order streaming. As we would expect, our algorithm performs better on random arrival streams.
Note that in terms of memory use, our algorithm is strictly more efficient. The analysis in previous sections show that the memory is Okk/c) (with small constant), versus O log k/s) for both SIEVESTREAMING and SALSA. Thus in the experiments below, we focus on the approximation ratio obtained by our algorithm.
accidents
chess
connect
250
125
200
100
objectie
150
objective
40
objective
75
lazy greedy sieve streaming
lazy greedy sieve streaming
lazy greedy
100
50
sieve streaming
20
50
salsa
25
salsa
our algorithm
algorithm
our algorithm
0
3
6
9
12
15
16
21
3
9
12 15
18
21
0
3
6
12
15
18
21
k
mushroom
pumsb
kosarak
12500
100
400
10000
abjective
7500
objective
75
objective
300
lazy greedy sieve streaming
lazy greedy sieve streaming
lazy greedy sieve streaming
5000
2500
salsa
25
salsa
100
salse
algorithm
our algorithm
our algorithm
0
3
12
18
21
12 15
pumsb star
retail
T40110D100K
1000
600
abjective
objective
750
objective
400
fazy greedy sieve streaming
500
azy greedy
Jazy greedy sieve streaming
sieve streaming
200
salsa our algorithm
250
saisa
salsa
our algorithm
our algorithm
3
6
12
15
18
21
6
9
12
15
18
21
0
3
6
9
12
15
18
21
Figure 1: Performance of lazy greedy, sieve streaming, and our algorithm on each data set (averaged across 10 runs, shaded regions represent variance across different random orderings).
*SIEVESTREAMING is also known as threshold greedy in the literature [BV14]. Note that the later SIEVESTREAMING++ algorithm of [KMZ* 19] is more efficient, but for approximation ratio SIEVESTREAMING is stronger benchmark.

---

Datasets Our datasets are drawn from set coverage instances from the 2003 and 2004 work- shops on Frequent Itemset Mining Implementations [oDM04] and the Steiner triple instances of Beasley [Bea87]. For each data set we run the three algorithms for cardinality constraints varying from
to 20. The results the algorithms are averaged across 10 random stream orderings. Ta- ble 2 describes the data sources. Figure shows the performance of the three algorithms on each data set. All code can found at https://sst //t::///ghhbb. wtw//wheeeeeeeeee wwweeeei--pralsuttleeeeeeee and all datasets can be found htttp:://tiinpie
com/neurips-22
dataset
source
# of sets
universe size
accidents
(anonymized) traffic accident data
340183
468
chess
UCI ML Repository
3196
75
connect
UCI ML Repository
67557
129
kosarak
(anonymized) click-stream data
990002
41270
mushroom
UCI ML Repository
8124
119
pumsb
census data for population and housing census data for population and housing
49046
7116
pumsb
49046
7116
retail
(anonymized) retail market basket data
88162
16469
T40110D100K
generator from IBM Quest research Table 2: Description of data sources for monotone experiments.
100000
999
Conclusion and Future Work
In this work, we have presented memory-optimal algorithms for the problem maximizing submodular functions with respect to cardinality constraints in the random order streaming model. Our algorithms achieve an optimal approximation factor of 1 1/e for the monotone submodular case, and an approximation factor of 1/e for the non-monotone case. In addition to theoretical guarantees, we show that the algorithm outperforms existing state-of-the-arr
variety of datasets.
We close with a few open questions that would make for interesting future work, Although our algo- rithm is memory-optimal, it is not runtime-optimal. In particular, the StEVESTREAMING [BMKK 14] and SALSA [NTM 18] algorithms both run time On log k/s), whereas our algorithm runs in time Onn/E & log k/e). The non-monotone variant of our algorithm runs even slower, as it needs to perform sub-sampling operations that take at least (:5/)) per stream element in its current form. Improving this runtime would greatly improve the practicality of our algorithm for extremely large cardinality constraints. Finally, there has been recent interest in examining streaming algorithms for streams under "adversarial injection" [GKRS20]. In such streams, the optimal elements of the stream randomly ordered, while adversarial elements can be injected between the optimal elements with no constraints. Despite the seemingly large power of the adversary, the 1/2 approximation barrier can still be broken in this model. It would be interesting to see if the work in this paper can be extended to such a setting.
Acknowledgments and Disclosure of Funding
The authors are indebted to Mohammad Shadravan and Morteza Monemizadeh for their insightful discussions that no doubt improved this work. The first author is supported by VMWare Fellowship and the Natural Sciences and Engineering Research Council of Canada. The second and fourth authors are supported by NSF CCF- 1954927, and the second author is additionally supported by a David and Lucile Packard Fellowship.
References
[AEF* 20] Naor Alaluf, Alina Ene, Moran Feldman, Huy Nguyen, and Andrew Suh. Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. arXiv:1911.12952 [cs], February 2020. arXiv: 1991..
[AF19] Naor Alaluf and Moran Feldman. Making a Sieve Random: Improved Semi- Streaming Algorithm for Submodular Maximization under a Cardinality Constraint. 1XXv:1906.11237 [cs], June 2019, arXiv: 1906.11233 1237.
10

---

[ASS19] Shipra Agrawal, Mohammad Shadravan, and Cliff Stein. Submodular Secretary Problem with Shortlists. In 10th Innovations Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of L.Plcs,, pages 1:1-1:19. Schloss Dagstuhl Leibniz-7Zentrum für Informatik, 2019.
[Bea87] J.E. Beasley. An algorithm for set covering problem. European Journal of Operational Research, (1))):85 93, 1987.
[BFNS14] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular Max- imization with Cardinality Constraints. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 435-1452. SIAM, 2014.
[BMKK14] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming Submodular Maximization: Massive Data Summarization on the Fly. Sofus Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang, and Rayid Ghani, editors, The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New York, NY, USA August 24 27, 2014, pages 671-680. ACM, 2014.
[BV14] Ashwinkumar Badanidiyuru and Jan Vondrák. Fast Algorithms for Maximizing Sub- modular Functions. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium Discrete Algorithmms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1497-1514. SIAM, 2014.
[CGQ15] Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for sub- modular function maximization. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming -42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Pro- ceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 318-330. Springer, 2015.
[Fei98] Uriel Feige. A Threshold of In for Approximating Set Cover. J. ACM, 45(4))6344652, 1998.
[FKK18] Moran Feldman, Amin Karbasi, and Ehsan Kazemi. Do less, get more: Streaming submodular maximization with subsampling. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Gesa-Bianchi and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pages 730-740, 2018
[FNSZ20] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The One- way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness. Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 363-1374, ACM, 2020.
[GKRS20]
Paritosh Garg. Sagar Kale, Lars Rohwedder, and Ola Svensson. Robust algorithms under adversarial injections. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Suarbrücken, Germany (Virtual Conference), volume 168 of LIPlcs, pages 56:1-56:1 Schloss Dagstuhl- Leibniz-Zentruu für Informatik, 2020.
[HKMY20] Chien-Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida. Ap- proximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model. arXivv2002..55777 [cs], February 2020.
arXiv: 2002.05477.
[HTW20] Chien-Chung Huang. Theophile Thiery, and Justin Ward. Improved multi-pass stream- ing algorithms for submodular maximization with matroid constraints. In Jaroslaw
11

---

Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPlcs, pages 12:11.. Schloss Dagstuhl- Leibniz-Zentruu für Informatik, 2020.
[IKBA20] Rishabh K. Iyer, Ninad Khargoankar, Jeff A. Bilmes, and Himanshu Asanani. Submodu- lar Combinatorial Information Measures with Applications in machine learning. CoRR, abx/2006.15412, 2020.
[IV19] Piotr Indyk and Ali Vakilian. Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACTTSSIAA Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 July 5, 2019, pages 200-217. ACM, 2019.
JKZ* 19] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular Streaming in All its Glory: Tight Approximation, Minimum Mem- ory and Low Adaptive Complexity. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3311-3320. PMLR, 2019.
[Min78] Michel Minoux. Accelerated greedy algorithms for maximizing submodular set func- tions. Optimization Techniques, pages 234 243, 1978.
[MV19] Andrew McGregor and Hoa T. Vu. Better Streaming Algorithms for the Maximum Coverage Problem. Theory Comput. Syst. 63(7):1595-1619) 2019.
18] Ashkan Norouzi-Farde Jakub Tarnawski. Slobodan Mitrovic, Amir Zandieh, Aidasadat Mousavifar, and Ola Svensson. Beyond 1/2-approximation for submodular maxi- mization massive data streams. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Leurning, ICML 2018, Stockhulmsmüssan Stockholm, Sweden, July 10-15 15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3826-3835. PMLR, 2018
[NW78] George L Nemhauser and Laurence Wolsey. Best algorithms for approximating the maximum of submodular set function. Mathematics of operations research, 3(3):177-188 1978.
[NWF78] George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An Analysis of Approximations for Maximizing Submodular Set Functions I. Math. Program., 14(1):265-294, 1978.
[oDM04] IEEE International Conference on Data Mining. Workshops on Frequent Itemset Mining Implementations, 2003 and 2004. http://fimi. uantwerpen. be/data/.
[Sha20] Mohammad Shadravan. Improved submodular secretary problem with shortlists. CoRR, abs/2010.01901, 2020.
12


Reviews:
[{"review_id": "qBqYkOWs1S3", "reviewer": "Reviewer_GbQb", "summary": "This paper studies the problem of maximizing a submodular function. For monotone submodular functions subject to a cardinality constraint, the paper gives a $(1-1/e-\\epsilon)$-approximation. The space requirement is $O(k/\\epsilon)$ where $k$ is the cardinality constraint. This is in contrast to a previous algorithm of Agrawal et al. which gave an algorithm with the same approximation ratio but with an exponential dependence on $\\epsilon$. Hence, the new algorithm obtains an exponential improvement on the dependence on $\\epsilon$. The new algorithm is also straightforward to implement. For the case of non-monotone submodular maximization subject to a cardinality constraint of size $k$, the authors gives an algorithm that achieves a $(1/e - \\epsilon)$-approximation with space complexity $O(k / \\epsilon)$.\n\nThe authors also prove a $(1-1/e+\\epsilon)$ hardness result for monotone submodular maximization. This improves upon the previous best hardness result of $0.7$.\n\nFinally, the authors show some experimental results and it is apparent that their algorithm performs quite well when compared to offline greedy.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n- The problem is interesting and well-motivated.\n- In the case of monotone submodular maximization, the present paper significantly improves over previously known results in terms of space requirements. This makes the algorithm a practical one.\n- In the case of non-monotone submodular maximization, the paper also gives a significant improvement over known results - in this setting, the approximation ratio is improved.\n- The algorithmic techniques are quite nice. Although it is straightforward to implement, it is quite non-trivial.\n- The hardness is improved from $0.7$ to a tight $1-1/e$.\n- The authors run some experiements and their algorithm shows good empirical performance.\n- The paper is written well.\n\n**Weaknesses** \\\nNo complaints about the paper.\n\n**Target Audience** \\\nThe paper will be of interest to other researchers working in submodular optimization.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "gzBfHrqx7xQ", "reviewer": "Reviewer_zv6j", "summary": "This paper considers cardinality constrained submodular maximization, both monotone and non-monotone, in the random streaming setting. In the random streaming setting the universe is received in a uniformly random permutation, as opposed to the adversarial setting where the universe could be received in any order.\n\nIn the random streaming setting, better approximation guarantees are possible compared to the adversarial setting (where 1/2 is the best possible). An algorithm developed by [ASS19] was shown to give a $1-1/e-\\epsilon$ guarantee for cardinality constrained monotone submodular maximization, but has memory exponential in $\\epsilon$ making it impractical. This paper introduces a streaming algorithm that gives the $1-1/e-\\epsilon$ needing only $O(k/\\epsilon)$ memory. They also prove $1-1/e$ is the best possible. Further, they introduce a streaming algorithm for the non-monotone version of the problem that gives a $1/e$ approximation guarantee also in $O(k/\\epsilon)$ memory.\n\nThe algorithms are analyzed empirically, and shown to be practical.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this is a good paper. There are clear theoretical improvements compared to related work. In particular, the memory is much improved compared to [ASS19] while maintaining equally good approximation ratio. In addition, it looks like this is the first paper to consider non-monotone SM in the random stream model. The techniques used to get these results look interesting to me.\n\nOriginality: [ASS19] is the only work that I know of that is very closely related, and this appears to have sufficiently original ideas compared to [ASS19], and has made a substantial improvement on the memory. The paper appears very original compared to works other than [ASS19] that I know of.\n\nQuality: The paper appears to be of good quality.\n\nClarity: This paper is exceptionally well-written.\n\nSignificance: The results are definitely of interest to the submodular optimization community. One limitation to its significance is that the approximation guarantees assume the random stream model, which may be relatively limiting, but I think the results are still significant.\n\nWeaknesses: The experimental results are only showing the objective value of the different algorithms. Why isn't the algorithm compared to SieveStreaming on memory used (or maybe it should be SieveStreaming++ if that is more efficient as far as memory)? Also, why not compare to [NTM+18]? In addition, in what sort of applications would we have a random streaming model?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "NGaMQ6L4wzV", "reviewer": "Reviewer_EsiB", "summary": "The paper studies the submodular maximization problem with a cardinality constraint in the random stream model where the algorithm makes a single pass over a random permutation of the elements. The main contribution of the paper is an algorithm for monotone functions with a nearly-optimal 1-1/e-eps approximation and O(k/eps) memory. The algorithm also extends to non-monotone functions via sub-sampling, giving a 1/e-eps approximation  using the same memory requirement. On the hardness side, the paper shows an unconditional hardness result showing that an approximation of 1+1/e is best possible for any single-pass random stream algorithm, even if the algorithm is allowed unbounded computation time.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Significance: The paper studies a well-motivated and widely studied problem and it achieves significant improvements over the state of the art. The proposed algorithms build on the prior work that shows an analogous approximation but using memory and time that is exponential in k and eps. In contrast, the proposed algorithm has essentially ideal memory requirement and the algorithm is efficient and practical. The experiments show that the algorithm outperforms the state of the art algorithm for arbitrary streams and its performance is close to that of the offline greedy algorithm. Overall, both the algorithmic and hardness contributions are a substantial addition to this line of work.\n\nNovelty/originality: The algorithms build on prior work but there is substantial novelty in the design and analysis of the algorithm that leads to the significantly improved memory and time efficiency. The algorithm is simple and easy to implement, and the main complexity lies in the analysis, which is intricate and requires novel ideas.\n\nClarity: The paper is well-written and clear. The paper provides ample intuition for the algorithm and the analysis, which make the paper accessible despite the fact that the analysis is intricate.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "I did not track the hours"}, "extra_text": {}}, {"review_id": "LJkF48ZSIEq", "reviewer": "Reviewer_QQMD", "summary": "This work studies cardinality-constrained submodular maximization in a one-pass\nstreaming model (with a random ordering). The main results are:\n- A $(1-1/e-\\varepsilon)$-approximation algorithm for monotone functions that\n  uses $O(k/\\varepsilon)$ memory, where $k$ is the cardinality constraint.\n- A $1/e$-approximation algorithm for non-monotone submodular functions that\n  also uses $O(k / \\varepsilon)$ memory.\n- A new hardness result which shows that any\n  $O(1-1/e+\\varepsilon)$-approximation algorithm requires $\\Omega(n)$ memory.\n\nThe algorithm for monotone functions in this paper improves on the recent work\nof [Agrawal-Shadravan-Stein, ITCS 2019] by removing an exponential dependency\non $\\varepsilon$ in the space complexity. Similarly, they close the previously\nbest-known streaming hardness gap of $7/8$ to $(1-1/e+\\varepsilon)$, which was\nalso proven in [Agrawal-Shadravan-Stein, ITCS 2019]. Lastly, the authors provide\na strong set of experiments that demonstrates their streaming algorithm is very\ncompetitive with an offline greedy algorithm.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality.**\nThis work directly builds on the recent work of [Agrawal-Shadravan-Stein, ITCS\n2019], and combines several techniques from the submodular maximization\nliterature to achieve state-of-the-art results when the elements arrive in a\nrandom stream. The originality of this paper is mostly due to the results the\nauthors achieved, as opposed to a new technique or hammer for future use.\n\n**Quality.**\nThis work is very high quality. It would be helpful to give the reader more\ncontext around the results in Section 4, but aside from that this is a nice,\nself-contained paper.\n\n**Clarity.**\nThis paper is very well written and easy to follow.\n\n**Significance.**\nThis paper is a great addition to the streaming submodular maximization\nliterature. Several recent works [NTM+18 (ICML), KMZ+19 (ICML), FNSZ20 (STOC)]\nhave studied submodular maximization in an adversarial stream, and [ASS19\n(ITCS)] recently explored what happens when the stream is a random permutation\nof the elements. This work answers many of the open questions in [ASS19].\n\n**Typos / Suggestions.**\n- [page 4] Typo: \"a evolving\" --> \"an evolving\"\n- [page 4] Typo: \"collection of partial solution\" --> \"collection of partial solutions\"\n- [page 5] $f(O)$ is used before $O$ is introduced as the OPT solution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agree that the paper makes substantial improvement over previous works in terms of memory requirement for an important problem.
Decision: Accept (Poster)