Chien-Chung Huang

Naonori Kakimura
email: kakimura@math.keio.ac.jp

Simon Mauras
email: simon.mauras@irif.fr

Yuichi Yoshida
email: yyoshida@nii.ac.jp

Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature.

In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat 1 -1 e in the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio 2 2+ √ 2 + ε requires Ω n K 2 space for any ε > 0, where K is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio K 2K-1 +ε requires Ω n K

space for any ε > 0, where K is the rank of the given matroid.

In addition, we give streaming algorithms when we only have a weak oracle with which we can only evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios K 2K-1 and 1 2 , respectively, whose space complexity is exponential in K but is independent of n. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of K 2K-1 for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of n.

Introduction

A set function f : 2 E → R on a ground set E is submodular if it satisfies the diminishing marginal return property, i.e., for any subsets S ⊆ T E and e ∈ E \ T , f (S ∪ {e})f (S) ≥ f (T ∪ {e})f (T ).

A function is monotone if f (S) ≤ f (T ) for any S ⊆ T ⊆ E. Submodular functions play a fundamental role in combinatorial optimization, as they capture rank functions of matroids, edge cuts of graphs, and set coverage, just to name a few examples.

In addition to their theoretical interests, submodular functions have attracted much attention from the machine learning community because they can model various practical problems such as online advertising [START_REF] Alon | Optimizing budget allocation among channels and influencers[END_REF][START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Soma | Optimal budget allocation: Theoretical guarantee and efficient algorithm[END_REF], sensor location [START_REF] Krause | Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies[END_REF], text summarization [START_REF] Lin | Multi-document summarization via budgeted maximization of submodular functions[END_REF][START_REF] Lin | A class of submodular functions for document summarization[END_REF], and maximum entropy sampling [START_REF] Lee | of Encyclopedia of Environmetrics[END_REF]. Many of these problems can be formulated as non-negative monotone submodular function maximization under a cardinality constraint or a matroid constraint. Namely, (Cardinality constraint) maximize f (S) subject to |S| ≤ K, S ⊆ E.

(

(Matroid constraint) maximize f (S) subject to S ∈ I, S ⊆ E,

where f : 2 E → R + is a monotone submodular function, K ∈ Z + is a non-negative integer, and M = (E, I) is a matroid with independent family I. Note that a matroid constraint includes a cardinality constraint as a special case: Choose the matroid in [START_REF] Badanidiyuru | Streaming submodular maximization: massive data summarization on the fly[END_REF] to be the uniform matroid of rank K.

In some applications mentioned before, the amount of input data is much larger than the main memory capacity of individual computers. Then, it is natural to consider the streaming model, where each item in the ground set E arrives sequentially, and we are allowed to use a small amount of memory. Unless stated otherwise, we always consider single-pass algorithms, that is, algorithms that scan the entire stream only once.

Submodular maximization under the streaming model has received much attention recently. Algorithms with various approximation ratios and space requirements have been proposed for the cardinality constraint [START_REF] Badanidiyuru | Streaming submodular maximization: massive data summarization on the fly[END_REF][START_REF] Kazemi | Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity[END_REF], the knapsack constraint [START_REF] Huang | Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[END_REF][START_REF] Huang | Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[END_REF][START_REF] Yu | Streaming algorithms for news and scientific literature recommendation: Submodular maximization with a d-knapsack constraint[END_REF], and the matroid constraint [START_REF] Chakrabarti | Submodular maximization meets streaming: matchings, matroids, and more[END_REF][START_REF] Chekuri | Streaming algorithms for submodular function maximization[END_REF]. However, there are only a few inapproximability results. McGregor and Vu [START_REF] Mcgregor | Better streaming algorithms for the maximum coverage problem[END_REF] showed that any streaming algorithm for maximizing a coverage function under a cardinality constraint with approximation ratio better than 1 -1 e requires Ω n K 2 space, where n := |E| is the number of elements. Norouzi-Fard et al. [START_REF] Norouzi-Fard | Beyond 1/2-approximation for submodular maximization on massive data streams[END_REF] showed that any streaming algorithm for maximizing a monotone submodular function under a cardinality constraint with approximation ratio better than K 2K-1

requires Ω n K space, assuming that we can only evaluate function values of feasible sets, which we call the weak oracle model. A standard value oracle is called strong for comparison.

Our contributions

The first contribution of this work is giving inapproximability results for cardinality and matroid constraints that beat 1 -1 e in the strong oracle model for the first time.

1

K 2K-1 -ε O K2 2K ε weak Theorem 1.4
Hardness

1 -1 -1 K K + ε, ∀ε > 0 Ω n K 2 strong [35] K 2K-1 + ε, ∀ε > 0 Ω n K weak [37] 2 2+ √ 2 + ε, ∀ε > 0 Ω n K 2
strong Theorem 1.2 Before explaining our results, we first note that, in the context of submodular maximization, it is standard to assume that a value oracle of a function f is given and the complexity of algorithms is measured based on the number of oracle calls [START_REF] Badanidiyuru | Streaming submodular maximization: massive data summarization on the fly[END_REF][START_REF] Chakrabarti | Submodular maximization meets streaming: matchings, matroids, and more[END_REF][START_REF] Chekuri | Streaming algorithms for submodular function maximization[END_REF][START_REF] Huang | Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[END_REF][START_REF] Huang | Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[END_REF][START_REF] Kazemi | Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity[END_REF][START_REF] Yu | Streaming algorithms for news and scientific literature recommendation: Submodular maximization with a d-knapsack constraint[END_REF]. However, a value oracle of f is too powerful in the streaming setting if we are allowed to put an exponential number of queries. In fact, if we have a free access to the value oracle, we can maximize f even without seeing the stream by querying about every subset. This observation leads to the following natural model, which we call the element-store model. Definition 1.1 (Element-store model). Let E = {e 1 , . . . , e n } be the ground set and f : 2 E → R + be a set function. A streaming algorithm in the element-store model maintains a set of elements S, which is initially an empty set, and possess an additional memory M . At step t ∈ {1, . . . , n}, the item e t is given to the algorithm, and the algorithm updates S and the content of M using the values of f (S ′ ) for S ′ ⊆ S ∪ {e t } and the content of M . Finally, the algorithm outputs a subset of S. The space complexity of the algorithm is the sum of the number of words stored in M and the maximum size of S over the n steps.

The weak oracle model is equivalent to constraining S always to be a feasible set. We note that all known streaming algorithms for submodular function maximization [START_REF] Badanidiyuru | Streaming submodular maximization: massive data summarization on the fly[END_REF][START_REF] Chakrabarti | Submodular maximization meets streaming: matchings, matroids, and more[END_REF][START_REF] Chekuri | Streaming algorithms for submodular function maximization[END_REF][START_REF] Huang | Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[END_REF][START_REF] Huang | Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[END_REF][START_REF] Kazemi | Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity[END_REF][START_REF] Yu | Streaming algorithms for news and scientific literature recommendation: Submodular maximization with a d-knapsack constraint[END_REF] lie in the element-store model. Now, we state our results. Theorem 1.2. For any K ∈ N and ε > 0, any (randomized) streaming algorithm for monotone submodular function maximization under a cardinality constraint in the element-store model with approximation ratio 2

2+ √ 2 + ε ≈ 0.585 + ε requires Ω n K 2 space.
Theorem 1.3. For any K ∈ N and ε > 0, any (randomized) streaming algorithm for monotone submodular function maximization under a partition matroid constraint in the element-store model with approximation ratio K 2K-1 + ε requires Ω n K space. Indeed, the same inapproximability results hold for any streaming algorithm in the elementstore model with unbounded computational power and memory space for M , as long as the number of elements stored in S is bounded. The proof techniques can be found in Section 1.2.

Next, we complement the previous and obtained inapproximability results by showing (weakoracle) streaming algorithms for cardinality and matroid constraints. We first present a weakoracle streaming algorithm for a cardinality constraint with approximation ratio K 2K-1ε, which is slightly better than the previous best approximation ratio of 1 2 [START_REF] Badanidiyuru | Streaming submodular maximization: massive data summarization on the fly[END_REF][START_REF] Kazemi | Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity[END_REF] and exactly matches the known inapproximability for the weak oracle model [START_REF] Norouzi-Fard | Beyond 1/2-approximation for submodular maximization on massive data streams[END_REF]. Although the space usage is exponential in K, it does not depend on the number of elements n. Then, we extend the algorithm given in Theorem 1.4 to a weak-oracle streaming algorithm for a matroid constraint with approximation ratio 1 2ε, which almost matches the inapproximability of K 2K-1 + ε given in Theorem 1.3. This almost settles the the approximation ratio for a matroid constraint that can be achieved by a streaming algorithm with space complexity independent of n, for both the weak and strong oracle models.

Theorem 1.5. There exists a weak-oracle 1 2ε -approximation streaming algorithm for monotone submodular function maximization under a matroid constraint with O K 5K+1 log(K/ε) ε space.

All the previous and obtained results are summarized in Table 1. Here, O(•) hides a polylogarithmic factor in K ε .

Our techniques

Lower bound construction We first describe the intuition behind our proof of Theorem 1.2. The elements of the ground set E are colored either blue, red, or purple, and we have a large number of n -K blue elements, K -1 red elements, and one purple element. Let B, R, and P be the set of blue, red, and purple elements, respectively, that is,

|B| = n -K, |R| = K -1,
and |P | = 1. We note that the colors of elements are not revealed to algorithms. We design our monotone submodular function f : 2 E → Z + so that it is colorwise-symmetric meaning that the value of f (S) is uniquely determined by the number of blue, red, and purple elements in a subset S. We write f (b, r, p) to denote the value of f (S) when there are b blue elements, r red elements, and p purple elements in S. We will assume that f (0, K -1, 1) gives the optimal value. In the input stream, blue and red elements arrive in a random order, and then the purple element arrives at the end. We design f so that it is hard to distinguish blue and red elements (without using the purple element). More precisely, f satisfies the property f (b + 1, 0, 0) = f (b, 1, 0) for any non-negative integer b. As the number of blue elements is much larger than that of red elements and the space is limited, with high probability, we must immediately throw away red elements from the memory right after they arrive. Thus, with high probability, we obtain the values f (K, 0, 0), f (K -1, 1, 0) or f (K -1, 0, 1), i.e., most of the time the algorithm ends up with at least K -1 blue elements. On the basis of some ideas suggested by computer simulations, we construct f so that the maximum of the three values is small.

The proof outline of Theorem 1.3 is similar, but is more involved. We first regard that the ground set

E is partitioned into classes C 1 , . . . , C K such that |C 1 | = • • • = |C K-1 | =: m and |C K | = 1,
and we constrain that the output set takes at most one element from each class, which is a partition matroid constraint. For each class i, there is a unique "right" element, referred to as the red element of the class, and for the first K -1 classes, there are a large number of "wrong" elements, referred to as blue elements of the class. We will define a monotone submodular function f : 2 E → R + whose value is determined by (1) the presence/absence of the red element of class from 1 to K, and (2) the number of blue elements of class from 1 to K -1. More precisely, given a set S, we denote by r i and b i the numbers of red and blue elements of class i in S for 1 ≤ i ≤ K, respectively, and then f (S) takes the form of f (r 1 , r 2 , . . . , r K ; b 1 , b 2 , . . . , b K ). We note that r i ∈ {0, 1} for all i, and b K should always be 0. We call such a function colorwise-symmetric with respect to the partition {C 1 , . . . , C K }. We will assume that f (1, . . . , 1; 0, . . . , 0) gives the optimal value.

In the input stream, for each i ∈ {1, . . . , K -1} in this order, the blue and red elements of class i arrive in a random order, and then the unique red element of class K arrives. We design f so that it is hard to distinguish blue and red elements in each class. More precisely, f satisfies the property

f (r 1 , . . . , r i-1 , 1, 0, . . . , 0; b 1 , . . . , b i-1 , b i , 0, . . . , 0)
=f (r 1 , . . . , r i-1 , 0, 0, . . . , 0; b 1 , . . . , b i-1 , b i + 1, 0, . . . , 0)

for any 1 ≤ i ≤ K -1, r 1 , . . . , r i-1 ∈ {0, 1}, and b 1 , . . . , b i ∈ {0, 1, . . . , m}. Combined with the monotonicity of f , we can show that the maximum value we can obtain via any algorithm is f (0, . . . , 0, 1; 1, . . . , 1, 0) with high probability. Again on the basis of some ideas suggested by computer simulations, we can construct f so that this value is small. We note that we took a different approach from the information-theoretic argument based on communication complexity used to show existing lower bounds [START_REF] Mcgregor | Better streaming algorithms for the maximum coverage problem[END_REF][START_REF] Norouzi-Fard | Beyond 1/2-approximation for submodular maximization on massive data streams[END_REF], because we wanted to show lower bounds when the value oracle for a submodular function is available, and it is not clear how we can integrate it in the communication complexity setting. In [START_REF] Mcgregor | Better streaming algorithms for the maximum coverage problem[END_REF], coverage functions were explicitly constructed from instances of a communication complexity problem, and hence we can regard that the sets used to define the coverage functions are given one by one in a streaming fashion, and we do not need the value oracle. In [START_REF] Norouzi-Fard | Beyond 1/2-approximation for submodular maximization on massive data streams[END_REF], the issue was avoided by assuming that the value oracle is weak.

Our algorithms Our algorithms for cardinality and matroid constraints, given in Theorems 1.4 and 1.5, all use branching, depending on the property of the first element o 1 of the optimal solution OPT in the stream. Here we explain the simplest case of cardinality constraint to highlight the basic ideas. We devise a general procedure which takes two parameters k and s. The former is the upper bound on the size of the optimal solution while the latter is the allowed size of the solution.

Such a procedure would guarantee that the returned solution achieves the approximation ratio of s k+s-1 , where we observe that the ratio improves when s is large relatively to k.

In the first branch, we assume that the value of o 1 is sufficiently large and we simply take the first element e whose value is above a certain threshold and then recurse on all the elements after e (with parameters k -1 and s -1). Doing this guarantees that the element we first take is of large value ("bang for the buck"), and more critically, o 1 (and hence the rest of OPT) is not "missed" in the recursion. In the second branch, we assume that the value of o 1 is too small and we can as well just focus on OPTo 1 , by recursing directly on all remaining elements (with parameters k -1 and s). Even though the value of OPTo 1 is slightly smaller than OPT, the approximation ratio for the recursion is improved, as the available space s grows relatively to the optimal solution size.

For the case of matroid constraint, the above branching strategy need more careful handling. It is based on the idea of taking the first element that resembles o 1 and use it to recurse on OPTo 1 .

There is an extra issue that the element e resembling o 1 may not form an independent set together with OPTo 1 . This issue is circumvented by using an extra set of candidates of o 1 , based on a known fact in matroid theory.

Related work

Maximizing a monotone submodular function subject to various constraints is a subject that has been extensively studied in the literature. Although the problem is NP-hard even for a cardinality constraint, it can be approximated in polynomial time within a factor of 1-1 e . See e.g., [START_REF] Badanidiyuru | Fast algorithms for maximizing submodular functions[END_REF][START_REF] Fisher | An analysis of approximations for maximizing submodular set functions I[END_REF][START_REF] Fisher | An analysis of approximations for maximizing submodular set functions II[END_REF][START_REF] Wolsey | Maximising real-valued submodular functions: primal and dual heuristics for location problems[END_REF]. On the other hand, even for a cardinality constraint, we need an exponential number of function evaluations to obtain approximation ratio better than 1-1 e [START_REF] Nemhauser | Best algorithms for approximating the maximum of a submodular set function[END_REF][START_REF] Vondrák | Symmetry and approximability of submodular maximization problems[END_REF]. Also, even when the submodular function is explicitly given (as a coverage function), Feige [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF] proved that the problem with a cardinality constraint cannot be approximated in polynomial time within a factor of 1 -1 e + ε for any constant ε > 0 unless P is equal to NP. Besides a cardinality constraint, the problem has also been studied under (multiple) matroid constraint(s), p-system constraint, multiple knapsack constraints. See [START_REF] Calinescu | Maximizing a monotone submodular function subject to a matroid constraint[END_REF][START_REF] Chan | Online submodular maximization with free disposal: Randomization beats for partition matroids online[END_REF][START_REF] Chan | Online submodular maximization problem with vector packing constraint[END_REF][START_REF] Chekuri | Submodular function maximization via the multilinear relaxation and contention resolution schemes[END_REF][START_REF] Ene | A nearly-linear time algorithm for submodular maximization with a knapsack constraint[END_REF][START_REF] Ene | Towards nearly-linear time algorithms for submodular maximization with a matroid constraint[END_REF][START_REF] Filmus | A tight combinatorial algorithm for submodular maximization subject to a matroid constraint[END_REF][START_REF] Kulik | Maximizing submodular set functions subject to multiple linear constraints[END_REF][START_REF] Lee | Submodular maximization over multiple matroids via generalized exchange properties[END_REF][START_REF] Yoshida | Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint[END_REF] and the references therein.

Multi-pass streaming algorithms, where we are allowed to read a stream of the input multiple times, have also been studied [START_REF] Badanidiyuru | Fast algorithms for maximizing submodular functions[END_REF][START_REF] Chakrabarti | Submodular maximization meets streaming: matchings, matroids, and more[END_REF][START_REF] Huang | Multi-pass streaming algorithms for monotone submodular function maximization[END_REF][START_REF] Huang | Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[END_REF]. In particular, Chakrabarti and Kale [START_REF] Chakrabarti | Submodular maximization meets streaming: matchings, matroids, and more[END_REF] gave an O(ε -3 )-pass streaming algorithms for a generalization of the maximum matching problem and the submodular maximization problem with cardinality constraint. Huang and Kakimura [START_REF] Huang | Multi-pass streaming algorithms for monotone submodular function maximization[END_REF] designed an O(ε -1 )-pass streaming algorithm with approximation guarantee 1/2-ε for the knapsackconstrained problem. Other than the streaming setting, recent applications of submodular function maximization to large data sets have motivated new directions of research on other computational models including parallel computation model such as the MapReduce model [START_REF] Barbosa | A new framework for distributed submodular maximization[END_REF][START_REF] Barbosa | The power of randomization: Distributed submodular maximization on massive datasets[END_REF][START_REF] Kumar | Fast greedy algorithms in MapReduce and streaming[END_REF] and the adaptivity analysis [START_REF] Balkanski | An exponential speedup in parallel running time for submodular maximization without loss in approximation[END_REF][START_REF] Balkanski | The adaptive complexity of maximizing a submodular function[END_REF][START_REF] Chekuri | Submodular function maximization in parallel via the multilinear relaxation[END_REF][START_REF] Ene | Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time[END_REF].

The maximum coverage problem is a special case of monotone submodular maximization under a cardinality constraint where the function is a set-covering function. For the special case, McGregor and Vu [START_REF] Mcgregor | Better streaming algorithms for the maximum coverage problem[END_REF] and Batani et al. [START_REF] Bateni | Almost optimal streaming algorithms for coverage problems[END_REF] gave a (1e -1ε)-approximation algorithm in the multi-pass streaming setting.

Organization

We prove our lower bound for strong-oracle algorithms for a cardinality constraint (Theorem 1.2) and a matroid constraint (Theorem 1.3) in Sections 2 and 3, respectively. We explain our weakoracle algorithms and analyze them (Theorems 1.4 and 1.5) in Section 4.

Lower Bounds for Cardinality Constraints

In this section, we prove Theorem 1.2. As described in the introduction, the ground set E is partitioned into a blue set B, a red set R, and a purple set P , where |B| = n-K, |R| = K -1, and

|P | = 1. We design a colorwise-symmetric function f : 2 E → Z + such that f (b + 1, 0, 0) = f (b, 1, 0)
for any non-negative integer b ≤ |B| -1 and the values f (K, 0, 0), f (K -1, 1, 0) and f (K -1, 0, 1) are small. More specifically, we show the following: Lemma 2.1. For any large enough integer n and any integer h ≥ K, there exists a colorwisesymmetric function f : 2 E → Z + with |E| = n that satisfies the following conditions.

(i) f is monotone submodular. (ii) [Indistinguishability] f (b + 1, 0, 0) = f (b, 1, 0) holds for all 0 ≤ b ≤ n -K -1. (iii) [Output value] f (K, 0, 0) = f (K-1, 1, 0) = hK+ (K-1)K 2 and f (K-1, 0, 1) = (K -1) 2 + h(h+1) 2 hold. (iv) [Optimal value] f (0, K -1, 1) = (K -1)(h + K -1) + h(h+1) 2 holds.
We defer the construction of our hard function and its analysis to Sections 2.1-2.3. Below we prove Theorem 1.2 using Lemma 2.1. We will use the following bound in the proof. Proposition 2.2. We have

1 - k 2 n n k k! ≤ n k ≤ n k k! . Proof. The claim holds from n k = k-1 i=0 (n -i) k! and n k ≥ k-1 i=0 (n -i) ≥ (n -k) k = 1 - k n k n k ≥ 1 - k 2 n n k .
Proof of Theorem 1.2. Let h ≥ K be an integer determined later, and let f : 2 E → Z + with |E| = n be the colorwise-symmetric function as in Lemma 2.1.

Let D be the uniform distribution over orderings (e 1 , . . . , e n ) of elements of E, conditioned on that e 1 , . . . , e n-1 include all the red and blue elements. Note that e n is the (unique) purple element. By Yao's minimax principle, to prove Theorem 1.2, it suffices to show that any deterministic streaming algorithm A with o n K 2 space on an input sampled from D does not achieve approximation ratio more than K 2K-1 in expectation. Let (e 1 , . . . , e n ) denote a sequence of elements sampled from D. Let S t be the set of elements that A holds after the t-th step, that is, the t-th element e t has arrived and A has updated the set of elements it holds (by adding e t and/or discarding elements already in the set). We define S 0 = ∅ for convenience, and note that an algorithm chooses a subset of S n as the output of A. Note also that, for each 1 ≤ t ≤ n, the set S t is completely determined by S t-1 and the values of f (S) and

f (S ∪ {e t }) (S ⊆ S t-1 ), as A is deterministic.
For a set of indices I ⊆ {1, . . . , n}, we define S I = {e i | i ∈ I}. Then, for t ∈ {0, 1, . . . , n -1}, we iteratively define a canonical set I * t of indices (not elements) as follows. First, we set

I * 0 = ∅. Then, for each 1 ≤ t ≤ n -1, we define I * t as the set of indices of elements in S t when A had S I * t-1
after the (t -1)-th step and all but at most one element in S I * t-1 ∪ {e t } are blue. Note that I * t is uniquely determined because A is deterministic, and by Property (ii) of Lemma 2.1, the value of f (S I ∪ {e t }) for I ⊆ I * t-1 is uniquely determined from the size of I. We say that A followed the canonical process if A holds the set S I * t after the t-th step for each

1 ≤ t ≤ n -1. For 1 ≤ t ≤ n -1, let X t be the event that S I *
t-1 has one or more red elements and e t is red. Then, the probability that A does not follow the canonical process is bounded by the probability that n-1 t=1 X t happens. First, we have

Pr[X t ] ≤ K-2 r=1 s r n-s-2 K-2-r n-1 K-1
, where s is the space usage of the algorithm, because the probability that S I * t-1 has r red balls and e t is red is at most s r n-s-2

K-2-r / n-1 K-1 .
Then by a union bound, we have

Pr n-1 t=1 X t ≤ n-1 t=1 Pr[X t ] ≤ (n -1) K-2 r=1 s r n-s-2 K-2-r n-1 K-1 ≤ (n -1) K-2 r=1 s r r! (n-s-2) K-2-r (K-2-r)! 1 -K 2 n (n-1) K-1 (K-1)! (By Proposition 2.2) = K -1 1 -K 2 n (n -1) K-2 K-2 r=1 K -2 r s r (n -s -2) K-2-r = K -1 1 -K 2 n (n -1) K-2 (n -2) K-2 -(n -s -2) K-2 = K -1 1 -K 2 n n -2 n -1 K-2 1 -1 - s n -2 K-2 ≤ K -1 1 -K 2 n s(K -2) n -2 (By (1 -x) d ≥ 1 -dx) = 1 1 -K 2 n O K 2 s n .
Let Y be the event that S I * n-1 has one or more red elements. We have

Pr[Y ] ≤ 1 - n-s-1 K-1 n-1 K-1 ≤ 1 - 1 -K 2 n-s (n-s-1) K-1 (K-1)! (n-1) K-1 (K-1)! (By Proposition 2.2) = 1 -1 - K 2 n -s 1 - s n -1 K-1 ≤ 1 -1 - K 2 n -s 1 - s(K -1) n -1 (By (1 -x) d ≥ 1 -dx) = K 2 n -s + 1 - K 2 n -s s(K -1) n -1 .
As long as K = o( √ n) and s = o n K 2 , the probability that none of X 1 , . . . , X n-1 , and Y happens is at least 1o(1) by setting the hidden constant in s to be small enough. If none of the events has happened, the algorithm A can only obtain values for sets S with S ⊆ S I * t-1 ∪ {e t } for some 1 ≤ t ≤ n and |S| ≤ K. As S I * t-1 ∪{e t } for any 1 ≤ t ≤ n-1 contains at most one red element and S I * n-1 contains no red element, the value of f (S) is upper-bounded by max{f (K, 0, 0), f (K -1, 1, 0), f (K -1, 0, 1)}, which is given by Property (iii) of Lemma 2.1. Recall that the optimal value is given by Property (iv) of Lemma 2.1. Therefore, the approximation ratio (in expectation over

D) is (1 -o(1)) • max hK + (K-1)K 2 , (K -1) 2 + h(h+1) 2 (K -1)(h + K -1) + h(h+1) 2 + o(1) • 1.
The ratio is minimized when

h is ⌊ √ 2(K -1)⌋ or ⌈ √ 2(K -1)⌉.
When K approaches to infinity, the ratio is

(1 -o(1)) • 2 2 + √ 2 + o(1) > 0.585,
as desired.

Construction of Hard Functions

We first define our function, and then describe the intuition behind the construction. The next two subsections give its correctness proof.

Definition 2.3. We define a colorwise-symmetric function f : 2 E → Z + recursively by its marginal return: Define f (0, 0, 0) = 0 and f (0, 0, 1) = h(h + 1) 2 .

We denote the marginal returns of f by

∆ r (b, r) = f (b, r + 1, 0) -f (b, r, 0) = f (b, r + 1, 1) -f (b, r, 1), ∆ b (b, 0, 0) = f (b + 1, 0, 0) -f (b, 0, 0), ∆ b (b, 0, 1) = f (b + 1, 0, 1) -f (b, 0, 1),
where they are defined by

∆ r (b, r) =          K -1 + h -b if 0 ≤ b ≤ h + r, K -1 -r+b-h 2 if h + r + 1 ≤ b ≤ h + 2(K -2) -r, 0 if h + 2(K -2) -r + 1 ≤ b, ∆ b (b, 0, 0)(= ∆ r (b, 0)) =          K -1 + h -b if 0 ≤ b ≤ h, K -1 -b-h 2 if h + 1 ≤ b ≤ h + 2(K -2), 0 if h + 2(K -2) + 1 ≤ b, ∆ b (b, 0, 1) =          K -1 if 0 ≤ b ≤ h, K -1 -b-h 2 if h + 1 ≤ b ≤ h + 2(K -2), 0 if h + 2(K -2) + 1 ≤ b.
The value f (b, r, p) is determined in the following way: we start with the "base value", f (0, 0, p) (the presence of the purple element), then add the blue elements one by one until there are b of them (each increasing the marginal value by ∆ b (i, 0, p) for 0 ≤ i ≤ b -1), and then add the red elements one by one until there are r of them (each increasing the marginal value by ∆ r (b, i) for 0 ≤ i ≤ r -1). In other words, we have

f (b, r, p) = f (0, 0, p) + b-1 j=0 ∆ b (j, 0, p) + r-1 i=0 ∆ r (b, i).
(3)

Ideas behind the function

We start with several simple observations. The marginal values ∆ b (b, 0, 0), ∆ b (b, 0, 1) and ∆ r (b, r) are monotonically non-increasing as the parameters b and r increase 1 . This conforms with the property of diminishing marginal return of a submodular function. The next thing to notice is that, by design, the values ∆ b (b, 0, 0) are exactly identical to ∆ r (b, 0).

So f (b + 1, 0, 0) = f (b, 0, 0) + ∆ b (b, 0, 0) = f (b, 0, 0) + ∆ r (b, 0) = f (b, 1, 0
) and this is required by Lemma 2.1(ii). We next explain why the marginal values ∆ b (b, 0, 0), ∆ b (b, 0, 1) and ∆ r (b, r) are chosen in such a manner. A concrete example can be very useful to reveal the patterns generated by them. Assume that K = 4 (thus 3 red elements and 1 purple element, and a large number of blue elements) and we choose h = 4. Table 2 gives the function values when the purple element is absent or present, along with ∆ r (b, r), the marginal value of adding a red element. We observe that for every fixed r,

= h + 2(K -2) -r. They follow because ∆r(h + r, r) = K -r -1 ≥ K -1 -⌈r + 1 2 ⌉ = ∆r(h + r + 1, r) and ∆r(h + 2(K -2) -r, r) = K -1 -⌈K -1⌉ ≥ 0 = ∆r(h + 2(K -2) -r + 1, r).
To see ∆r(b, r) ≥ ∆r(b, r + 1), the only tricky cases are when b = h + r + 1 and when b = h + 2(K -2)r. It holds that ∆r(h + r + 1, r) = K -1r -1 = ∆r(h + r + 1, r + 1) and ∆r(h + 2(K -2)r, r) = 1 ≥ 0 = ∆r(h + 2(K -2)r, r + 1). beyond h + r, the same value ∆ r (b, r) appears twice before decreasing. Notice that the smaller the r = i, ∆ r (b, i) decreases in b more slowly (conforming with the submodularity).

Table 2: The function values along with the marginal value ∆ r (b, r) when K = h = 4. After the value b = h + r (we color it specially), the same ∆ r (b, r)'s appear twice before decreasing. Also notice that the values Indeed we choose all marginal values ∆ r (b, r), ∆ b (b, 0, 0) and ∆ b (b, 0, 1) with two objectives. (1) The indistinguishability of red and blue elements (i.e., Lemma 2.1(ii)), which forces ∆ r (b, 0) = ∆ b (b, 0, 0), and (2) creating a particular pattern of f (b, K -1, 0) and f (b, K -1, 1). As can be observed in this example, f (b, K -1, 1) is simply the optimal value for all b, while f (b, K -1, 0) increases by the amount of h, h -1, down to 1 when b increases from 0 to h and stop growing when b is beyond h. The fact that we want f (b, K -1, 0) to stop growing when b is beyond h explains why ∆ r (b, r) behaves somehow differently when b is beyond h + r.

f (b + 1, 0, 0) = f (b, 1, 0) for all 0 ≤ b ≤ n -K -1 (Lemma 2.1(ii)). p = 0 r = 0 r = 1 r = 2 r = 3 b f ∆ r f ∆ r f ∆ r f 0 0 7 7 7 14
p = 1 r = 0 r = 1 r = 2 r = 3 b f ∆ r f ∆ r f ∆ r f 0

Correctness of Function Values

In this section, we show that the function f defined in Definition 2.3 satisfies Lemma 2.1 (ii)-(iv).

Since ∆ b (b, 0, 0) = ∆ r (b, 0) for each b, we immediately have (ii) of Lemma 2.1. Moreover, it follows from (3) that

f (K, 0, 0) = K-1 j=0 ∆ b (j, 0, 0) = hK + (K -1)K 2 , f (K -1, 1, 0) = ∆ r (K -1, 0) + K-2 j=0 ∆ b (j, 0, 0) = K-1 j=0 ∆ b (j, 0, 0) = hK + (K -1)K 2 , f (K -1, 0, 1) = K-2 j=0 ∆ b (j, 0, 1) + f (0, 0, 1) = (K -1)(K -1) + h(h + 1) 2 .
It also holds that

f (0, K -1, 1) = K-2 i=0 ∆ r (0, i) + f (0, 0, 1) = (K -1)(h + K -1) + h(h + 1) 2 .
Thus (iii) and (iv) of Lemma 2.1 follow.

Monotonicity and Submodularity

Below we prove Lemma 2.1 (i), that is, the function f defined in Definition 2.3 is monotone and submodular. To this end, it suffices to show the following lemma.

Lemma 2.4. Let f : 2 E → Z + be the colorwise-symmetric function defined in Definition 2.3. Then we have

1. f (b 1 , r 1 , 1) -f (b 1 , r 1 , 0) ≥ f (b 2 , r 2 , 1) -f (b 2 , r 2 , 0) ≥ 0 for 0 ≤ b 1 ≤ b 2 ≤ |B| and 0 ≤ r 1 ≤ r 2 ≤ |R|. 2. f (b 1 , r 1 + 1, p 1 ) -f (b 1 , r 1 , p 1 ) ≥ f (b 2 , r 2 + 1, p 2 ) -f (b 2 , r 2 , p 2 ) ≥ 0 for 0 ≤ b 1 ≤ b 2 ≤ |B|, 0 ≤ r 1 ≤ r 2 ≤ |R| -1, and 0 ≤ p 1 ≤ p 2 ≤ 1. 3. f (b 1 + 1, r 1 , p 1 ) -f (b 1 , r 1 , p 1 ) ≥ f (b 2 + 1, r 2 , p 2 ) -f (b 2 , r 2 , p 2 ) ≥ 0 for 0 ≤ b 1 ≤ b 2 ≤ |B| -1, 0 ≤ r 1 ≤ r 2 ≤ |R|, and 0 ≤ p 1 ≤ p 2 ≤ 1.
Proof.

(1) By definition, it holds that, for ℓ = 1, 2,

f (b ℓ , r ℓ , 1) -f (b ℓ , r ℓ , 0) = b ℓ -1 j=0 ∆ b (j, 0, 1) -∆ b (j, 0, 0) + f (0, 0, 1) -f (0, 0, 0). Since ∆ b (j, 0, 0) = ∆ b (j, 0, 1) if j ≥ h + 1, the RHS is equal to min{b ℓ -1,h} j=0 K -1 -(K -1 + h -j) + h(h + 1) 2 ≥ - h j=0 (h -j) + h(h + 1) 2 = 0.
Hence the marginal return with respect to p is non-negative. Moreover,

f (b 1 , r 1 , 1) -f (b 1 , r 1 , 0) -f (b 2 , r 2 , 1) -f (b 2 , r 2 , 0) = min{h,b 2 -1} j=min{h,b 1 -1} (h -j) ≥ 0,
since hj ≥ 0 for j ≤ h. Thus (1) holds.

(2) We observe that ∆ r (b, r) is a monotonically non-increasing function with respect to b, and a monotonically non-increasing function with respect to r (See the footnote in Section 2.1.1). Hence it holds that

∆ r (b 1 , r 1 ) ≥ ∆ r (b 1 , r 2 ) ≥ ∆ r (b 2 , r 2 ) ≥ 0.
This implies that

f (b 1 , r 1 + 1, p 1 ) -f (b 1 , r 1 , p 1 ) = ∆ r (b 1 , r 1 ) ≥ ∆ r (b 2 , r 2 ) = f (b 2 , r 2 + 1, p 2 ) -f (b 2 , r 2 , p 2 ) ≥ 0.
Thus (2) holds.

(3) We first observe the following claims.

Claim 1. Let 0 ≤ r ≤ |R|.

1. For 0 ≤ b ≤ h + r -1, it holds that 2∆ r (b + 1, r) = ∆ r (b, r) + ∆ r (b + 2, r). 2. For h + r ≤ b, it holds that ∆ r (b, r) = ∆ r (b + 1, r -1)
∆ r (b, r) = ∆ r (b + 1, r -1) = K -1 -r. Claim 2. For 0 ≤ b ≤ |B| -2, 0 ≤ r ≤ |R|, and 0 ≤ p ≤ 1, it holds that f (b + 1, r, p) -f (b, r, p) ≥ f (b + 2, r, p) -f (b + 1, r, p) ≥ 0.
Proof. We first consider the case when b ≤ h + r -2. We will show that the first inequality holds by induction on r. The inequality holds when r = 0 as ∆ b (b, 0, p) ≥ ∆ b (b + 1, 0, p). Suppose that r > 0. Then we have

f (b + 1, r, p) -f (b, r, p) = f (b + 1, r -1, p) + ∆ r (b + 1, r -1) -f (b, r -1, p) + ∆ r (b, r -1) ≥ f (b + 2, r -1, p) + ∆ r (b + 1, r -1) -f (b + 1, r -1, p) -∆ r (b, r -1) = f (b + 2, r, p) -f (b + 1, r, p) + 2∆ r (b + 1, r -1) -∆ r (b, r -1) -∆ r (b + 2, r -1),
where the inequality holds by the induction hypothesis. Therefore, it follows from Claim 1 (1) that for 0

≤ b ≤ h + r -2, f (b + 1, r, p) -f (b, r, p) ≥ f (b + 2, r, p) -f (b + 1, r, p).
Thus, the claimed inequality holds when b ≤ h + r -2. This implies that, for 0

≤ b ≤ h + r -2, we have f (b + 1, r, p) -f (b, r, p) ≥ f (h + r + 1, r, p) -f (h + r, r, p).
Next suppose that h + r -1 ≤ b. We may assume that r > 0, as the case when r = 0 easily follows. By definition, it holds that

f (b + 1, r, p) -f (b, r, p) = r-1 i=0 ∆ r (b + 1, i) -∆ r (b, i) + ∆ b (b, 0, p). Since ∆ r (b, i) = ∆ r (b + 1, i -1) for i = 1, . . . , r -1 by Claim 1 (2), we have f (b + 1, r, p) -f (b, r, p) = ∆ r (b + 1, r -1) -∆ r (b, 0) + ∆ b (b, 0, p) = ∆ r (b + 1, r -1),
where the last equality follows from ∆ r (b, 0

) = ∆ b (b, 0, p) for b ≥ h. Similarly, f (b + 2, r, p) -f (b + 1, r, p) = ∆ r (b + 2, r -1). Hence f (b + 1, r, p) -f (b, r, p) = ∆ r (b + 1, r -1) ≥ ∆ r (b + 2, r -1) = f (b + 2, r, p) -f (b + 1, r, p).
Thus the claimed inequality holds.

Moreover, for h

+ r -1 ≤ b ≤ |B| -2, we have f (b + 1, r, p) -f (b, r, p) ≥ f (|B|, r, p) -f (|B| - 1, r, p) = ∆ r (|B|, r -1) ≥ 0.
Thus the monotonicity also holds.

Claim 3. For 0 ≤ b ≤ |B| -1, 0 ≤ r ≤ |R|, and 0 ≤ p ≤ 1, it holds that f (b + 1, r, 0) -f (b, r, 0) ≥ f (b + 1, r, 1) -f (b, r, 1).
Proof. We will show the claim by induction on r. The inequality holds when r = 0 as ∆ b (b, 0, 0) ≥ ∆ b (b, 0, 1). Suppose that r > 0. Then

f (b + 1, r, 0) -f (b, r, 0) = (f (b + 1, r -1, 0) + ∆ r (b + 1, r -1)) -(f (b, r -1, 0) + ∆ r (b, r -1)) ≥ f (b + 1, r -1, 1) + ∆ r (b + 1, r -1) -f (b, r -1, 1) -∆ r (b, r -1) = f (b + 1, r, 1) -f (b, r, 1),
where the inequality holds by the induction hypothesis. Thus the claim holds.

It holds that, for 0 ≤ b ≤ |B| -1, 0 ≤ r 1 ≤ r 2 ≤ |R|, and 0 ≤ p ≤ 1,

f (b + 1, r 1 , p) -f (b, r 1 , p) ≥ f (b + 1, r 2 , p) -f (b, r 2 , p), (4)
since

f (b + 1, r ℓ , p) -f (b, r ℓ , p) = r ℓ -1 i=0 (∆ r (b + 1, i) -∆ r (b, i)) + ∆ b (b, 0, p) for ℓ = 1, 2.
Therefore, applying Claims 2 and 3 with (4), we have

f (b 1 + 1, r 1 , p 1 ) -f (b 1 , r 1 , p 1 ) ≥ f (b 1 + 1, r 2 , p 1 ) -f (b 1 , r 2 , p 1 ) ≥ f (b 2 + 1, r 2 , p 1 ) -f (b 2 , r 2 , p 1 ) ≥ f (b 2 + 1, r 2 , p 2 ) -f (b 2 , r 2 , p 2 ).
Since the monotonicity follows by Claim 2, we complete the proof of (3).

Lower Bounds for Matroid Constraints

In this section, we prove Theorem 1.3. As described in the introduction, we assume that the ground set

E is partitioned into classes C 1 , . . . , C K such that |C 1 | = • • • = |C K-1 | =: m and |C K | = 1.
Note that the number of elements n := |E| is (K -1)m + 1. We design a monotone submodular function f : 2 E → Z + that is colorwise-symmetric with respect to the partition {C 1 , . . . , C K } such that it is hard to distinguish blue and red elements in each class whereas we need to hit all the red elements to get the optimal value. We will specify the exact values of f in the next section. Here, we summarize the critical properties of f and use them to prove Theorem 1.3.

Lemma 3.1. For any large enough integer m and any positive integer K, there exists a colorwisesymmetric function

f : 2 E → Z + with respect to a partition E = K i=1 C i with |C 1 | = • • • = |C K-1 | = m and |C K | = 1 such that (i) f is monotone submodular. (ii) [Optimal value] f (1, . . . , 1; 0, . . . , 0) = (2K -1)!.
(iii) [Output value] f (0, . . . , 0, 1; 1, . . . , 1, 0) = K(2K -2)!.

(iv) [Indistinguishability] For any 1 ≤ i ≤ K -1 and r 1 , . . . , r i-1 , b 1 , . . . , b i , we have

f (r 1 , . . . , r i-1 , 1, 0, . . . , 0; b 1 , . . . , b i-1 , b i , 0, . . . , 0) =f (r 1 , . . . , r i-1 , 0, 0, . . . , 0; b 1 , . . . , b i-1 , b i + 1, 0, . . . , 0).
Proof of Theorem 1.3. We modify the proof of Theorem 1.2.

Let f : 2 E → Z + be the function as in Lemma 3.1. For

1 ≤ i ≤ K -1, let T i = {(i -1)m +
1, . . . , im} and let T K = {n}. Let D be the uniform distribution over orderings (e 1 , . . . , e n ) of elements of E, conditioned on that for each 1 ≤ i ≤ K, the set {e t | t ∈ T i } consists of all the elements of class i. By Yao's minimax principle, to prove Theorem 1.3, it suffices to show that any deterministic streaming algorithm A with o n K space on an input sampled from D does not achieve approximation ratio more than K 2K-1 in expectation. We define S t for t ∈ {0, 1, . . . , n} and S I for I ⊆ {1, . . . , n} as in the proof of Theorem 1.2. For t ∈ {0, 1, . . . , n -1}, we iteratively define a canonical set I * t of indices (not elements) as follows. First, we set I * 0 = ∅. Then, for each 1 ≤ t ≤ n -1, we define I * t as the set of indices of elements in S t when A had S I * t-1 after the (t -1)-th step and all but at most one element in S I * ∪ {e t } are blue. Note that I * t is uniquely determined because A is deterministic, and by Property (iv) of Lemma 3.1, the value of f (S I ∪ {e t }) for I ⊆ I * t is uniquely determined from the sizes of I ∩ T 1 , . . . , I ∩ T K-1 . We say that A followed the canonical process if A holds the set S I * t after the t-th step for each 1 ≤ t ≤ n -1. For 1 ≤ t ≤ n -1, let X t be the event that S I * t-1 has one or more red elements and e t is red. Then, the probability that A does not follow the canonical process is bounded by the probability that n-1 t=1 X t happens. To bound Pr[X t ], we introduce some notations. Let s be the space usage of the algorithm.

For i ∈ {1, . . . , K -1}, let s i = |I * t-1 ∩ T i |.
For t ∈ {1, . . . , n -1}, let i t ∈ {1, . . . , K -1} be the class that the t-th element belongs to, that is, the unique integer i with t ∈ T i . Then for any t ∈ {1, . . . , n -1}, we have

Pr[X t ] ≤ K-2 r=1 max r 1 ,...,r K-1 ∈{0,1}: i =i t r i ≤r s it m i =it s r i i (m -s i ) 1-r i m ≤ K-2 r=1 s r r m K-2-r m K-1 = 1 m K-2 r=1 s rm r ≤ s m(m -s) = O s m 2 .
Here, we regard r as the number of red elements in S I * t-1 and regard r 1 , . . . , r K-1 ∈ {0, 1} as the numbers of red elements in S I * t-1 ∩T 1 , . . . , S I * t-1 ∩T K-1 , respectively. The first inequality holds because the probability that e t is red is

s i t
m and the probability that S I * t-1 ∩T i has r i red elements is

s r i i (m-s i ) 1-r i m
. Now by a union bound, we have

Pr n-1 t=1 X t ≤ n-1 t=1 Pr[X t ] = O sn m 2 = O Ks m .
Let Y be the event that S I * n-1 has one or more red elements. Then, we have

Pr[Y ] ≤ 1 - K-1 i=1 m -s i m ≤ 1 - (m -s)m K-2 m K-1 = s m .
As long as Ks = o(n), the probability that none of X 1 , . . . , X n-1 , and Y happens is at least 1) by setting the hidden constant in s to be small enough. If none of the events has happened, the algorithm A can only obtain values for sets S with S ⊆ S I * t-1 ∪ {e t } for 1 ≤ t ≤ n and |S| ≤ K. As S I * t-1 ∪ {e t } for any 1 ≤ t ≤ n -1 contains at most one red element and S I * n-1 contains no red element, the values the algorithm can observe is at most K(2K -2)! by Properties (iii) and (iv) of Lemma 3.1. Recall that the optimal value is (2K -1)! by Property (ii) of Lemma 3.1. Therefore, the approximation ratio (in expectation over D) is

1 -o(
(1 -o(1)) • K(2K -2)! (2K -1)! + o(1) • 1 = (1 -o(1)) K 2K -1 + o(1).

Construction of the Hard Function

We begin by describing some characteristics of the function we will define. Let bi = min{b i , 2(Ki)}. The function will be expressed as a polynomial of r i and bi for all 1 ≤ i ≤ K. In other words, the number of blue elements matter only up to a certain ceiling: For class i, if there are more than 2(Ki) blue elements in the class i, the function value is the same as if there are exactly 2(Ki) blue elements. To be more precise, we decree that

f (r 1 , • • • r K ; b 1 , . . . , b K ) = f (r 1 , . . . , r K ; b1 , . . . , bK ).
We now define the function f recursively. For t = 1, . . . K, let f t be a function on the last t classes C K-(t-1) , . . . , C K , that is, f t takes the form of

f t (r K-(t-1) , . . . , r K ; b K-(t-1) , . . . , b K ) Define f 1 (r K ; b K ) = r K ,
and assume the function f t-1 is already defined for some t ≥ 2. We then define the function f t . For that purpose, we give some notation. Let m t = (2t -1)!. As we will see later, the function value of f t-1 is between 0 and m t-1 . Suppose that we are given r K-(t-1) , r K-(t-2) , . . . , r K and b

K-(t-1) , b K-(t-2) , . . . , b K . Define 2 δ t-1 = m t-1 -f t-1 (r K-(t-2) , . . . , r K ; bK-(t-2) , . . . , bK ).
We also define

d t = 2(t -1) -bK-(t-1) and s t = 1 -r K-(t-1) .
The term d t (resp., s t ) is simply the gap between bK-(t-1) (resp., r K-(t-1) ) and its potential maximum. We remark that both of them are non-negative, and bK-(t-1) + d t = 2(t -1) and r K-(t-1) + s t = 1. We can then express f t as follows:

f t (r K-(t-1) , . . . , r K ; b K-(t-1) , . . . , b K ) = m t -a t • d t , (5)
where

a t = 2m t-1 s t + δ t-1 (d t -1).
The function f t is set up in such a way so that f t (1, . . . , 1; 0, . . . , 0) is exactly m t = (2t -1)! for any t. As we will show, this maximizes f t . On the other hand, f t (0, . . . , 0; 0, . . . , 0) = 0, which is the minimum of f t . To see the significance of the term a t , recall that the term δ t-1 encodes the difference between the maximum of f t-1 and the actual value attained by the given r K-(t-2) , . . . , r K and bK-(t-2) , . . . , bK -therefore always non-negative. Then we can regard a t as a linear combination of s t and d t (both are decided by the number of red/blue elements of class K -(t-1)), where the coefficients are respectively 2m t-1 and δ t-1 (both are decided by the number of red/blue elements from later classes K -(t -1) + 1, . . . , K). See Lemma 3.4 for a more precise summary of the above discussion.

Concrete Example and Some Observations

We present a concrete example to highlight several interesting properties of the function constructed in Section 3.1, and to share some of our experiences in searching for such a function. Let K = 3. 3 and4. We remark that having more blue elements does not increase the value further, as mentioned in Section 3.1.

All the function values when

0 ≤ b 1 ≤ 2(K -1) = 4 and 0 ≤ b 2 ≤ 2(K -2) = 2 are shown in Tables
We can first observe that, individually, the values of a single red/blue element of the first K -1 classes are all equal, and the value of the unique red element in the last class is half of them. In the present example, an element in the first two classes has value 48 while an element in the last class has value 24. In fact, we have the following observation for the constructed function f . Note that b K should always be 0. Table 3: When the unique element of C 3 is absent, i.e., r 3 = 0. Table 4: When the unique element of C 3 is present, i.e., r 3 = 1.

r 1 = 0, r 2 = 0 r 1 = 1, r 2 = 0 r 1 = 0, r 2 = 1 r 1 = 1, r 2 = 1 ❍ ❍ ❍ ❍ ❍ b1 b2 0 1 2 ❍ ❍ ❍ ❍ ❍ b1 b2 0 1 2 ❍ ❍ ❍ ❍ ❍ b1 b2 0 1 2 ❍ ❍ ❍ ❍ ❍ b1 b2 0
r 1 = 0, r 2 = 0 r 1 = 1, r 2 = 0 r 1 = 0, r 2 = 1 r 1 = 1, r 2 = 1 ❍ ❍ ❍ ❍ ❍ b1 b2 0 1 2 ❍ ❍ ❍ ❍ ❍ b1 b2 0 1 2 ❍ ❍ ❍ ❍ ❍ b1 b2 0 1 2 ❍ ❍ ❍ ❍ ❍ b1 b2 0
Lemma 3.2. The constructed function f satisfies the following.

f (0, . . . , 0, 1, 0, . . . , 0; 0, . . . , 0) =

   (2K -2)! if 1 is at the last class K 2(2K -2)! otherwise
f (0, . . . , 0; 0, . . . , 0, 1, 0, . . . , 0) = 2(2K -2)!,

The proof will be given in Section 3.4.

In the present example, the optimal value is 120, which is reached by a set of 2(K -1) blue elements of class 1, i.e, f (0, 0, 0; 4, 0, 0) = 120, though it is infeasible. The optimal value is also obtained by a set of all the red elements, which is equal to the sum of the values of each red element. In the example, we see that f (1, 1, 1; 0, 0, 0) = f (1, 0, 0; 0, 0, 0) + f (0, 1, 0; 0, 0, 0) + f (0, 0, 1; 0, 0, 0) = 48 + 48 + 24 = 120. Lemma 3.3. The constructed function f satisfies that f (1, . . . , 1; 0, . . . , 0) = f (1, 0, . . . , 0; 0, . . . , 0) + f (0, 1, 0, . . . , 0; 0, . . . ,

0) + • • • • • • + f (0, . . . , 0, 1; 0, . . . , 0) = (2K -1)!, f (0, . . . , 0; 2(K -1), 0, . . . , 0) = (2K -1)!.
The proof will be given in Section 3.4.

By the construction, the function f (r 1 , r 2 , r 3 ; b 1 , b 2 , b 3 ) can be expressed as the following polynomial:

f (r 1 , r 2 , r 3 ; b 1 , b 2 , b 3 ) = m 3 -(2m 2 s 3 + (2m 1 s 2 + s 1 (d 2 -1)) d 2 (d 3 -1)) • d 3 = 120 -(12s 3 + (2s 2 + s 1 (d 2 -1)) d 2 (d 3 -1)) • d 3 , (6)
where we recall that m t = (2t -1)!, d t = 2(t -1) -bK-(t-1) and s t = 1r K-(t-1) for t = 1, 2, 3. We can observe that f is a polynomial in s i 's and d i 's, where, for each monomial, s i 's have degree at most 1 and d i 's have degree at most 2. This implies that the discrete second derivative with respect to b i 's is constant when b i is in [0, 2(Ki)]. Take the current example with r 1 = r 2 = r 3 = b 2 = 0. When b 1 increases from 0 to 4, the discrete first derivative is 48, 36, 24, 12 and the discrete second derivative is a constant, which is 12. It can be verified that the same property holds for all columns and all rows in Tables 3 and4. In fact, we noticed in computer-aided search that imposing the additional constraint of constant second derivative does not change the ratio between the optimal value and the value an algorithm finds, making the found function more structured and generalizable. Based on computer-aided search imposing this additional constraint for small values of rank K, we found the recurrence in the previous section.

Correctness of the Function

We first show the monotonicity of the constructed function f t , which implies Lemma 3.1 (i) and (ii) when t = K. Lemma 3.4. For any t = 1, 2, . . . , K, the constructed function f t satisfies the following.

1. f t is monotone in r K-(t-1) , . . . , r K and in b K-(t-1) , . . . , b K .

2. f t reaches the maximum, which is m t = (2t -1)!, when r K-(t-1) = • • • = r K = 1.

f t reaches the minimum, which is

0, when r K-(t-1) = • • • = r K = b K-(t-1) = • • • = b K = 0.
Proof. We prove by induction on t. When t = 1, it is straightforward to verify the lemma. Consider when t ≥ 2.

For (1), suppose that

r 1 K-(t-1) ≥ r 2 K-(t-1) , • • • , r 1 K ≥ r 2 K and b 1 K-(t-1) ≥ b 2 K-(t-1) , • • • , b 1 K ≥ b 2 K . For ℓ = 1, 2, let δ ℓ t-1 , d ℓ t ,
0 ≤ δ 1 t-1 ≤ δ 2 t-1 . Furthermore, as b 1 K-(t-1) ≥ b 2 K-(t-1) , we have b1 K-(t-1) ≥ b2 K-(t-1) , implying that d 1 t ≤ d 2 t . Now it holds by (5) that f 1 t -f 2 t = δ 2 t-1 (d 2 t -1)d 2 t -δ 1 t-1 (d 1 t -1)d 1 t + 2m t-1 s 2 t d 2 t -s 1 t d 1 t ≥ δ 2 t-1 (d 2 t -1)d 2 t -δ 1 t-1 (d 1 t -1)d 1 t ≥ δ 1 t-1 (d 2 t -1)d 2 t -(d 1 t -1)d 1 t ≥ 0
where the first inequality holds because s 2 t ≥ s 1 t and d 2 t ≥ d 1 t , the second inequality is from δ 2 t-1 ≥ δ 1 t-1 , and the last inequality follows from the fact that the function x(x -1) is monotonically increasing for a non-negative integer x. (1) is then proved.

For (2), when

r K-(t-1) = r K-(t-2) = • • • = r K = 1
, by the induction hypothesis, f t-1 takes the maximum m t-1 , and hence δ t-1 = 0. Then a t = 0, since s t = 0 and δ t-1 = 0. Hence the f t -value Whenever OPT is non-empty, we denote by o 1 the first element that arrives in the stream among all elements in OPT.

In the description of the algorithms, we assume that we are given an approximate v ∈ R + so that v ≤ f (OPT) ≤ (1 + ε)v. and we will explain in Section 4.3 how to implement them without knowing the value v.

Cardinality Constraint

We start by defining the main procedure Cardinality. The procedure takes four parameters k, s, v, and g; we assume that OPT satisfies the conditions that g(OPT) ≥ v and |OPT| ≤ k, and s is an upper bound that we impose on the size of the returned solution of Cardinality(k, s, v, f ).

Cardinality(k, s, v, g) is described in Algorithm 1. Its basic idea can be simply described as follows. We target the approximation ratio of s s+k , which, intuitively, states that the ratio should get better as the allowed solution size s is increased with respect to k, the upper bound on the size of OPT. In case that k or s = 1, we simply choose the element that gives the largest g-value. So assume that k, s ≥ 2.

Depending on the value of g(o 1 ) (for which we have no prior knowledge), we create two branches:

• Branch 1: If g(o 1
) is sufficiently large (precisely at least v k+s-1 ), we just take the first element e so that g(e) ≥ v k+s-1 . Then e precedes o 1 (or is just o 1 ) and the rest of OPT. We define a new submodular function g ′ = g(• | e). We then invoke Cardinality(k, s -1, vg(e), g ′ ).

• Branch 2: If g(o 1 ) is too small, we simply ignore it and invoke Cardinality(k -1, s, k+s-2 k+s-1 v, g) directly.

The output is just the better outcome of the two branches. Lemma 4.1. Suppose that k ≥ 1 and s ≥ 1. Suppose that there is a set OPT in the input stream so that g(OPT) ≥ v and |OPT| ≤ k. Then Cardinality(k, s, v, g) returns a solution S such that g(S) ≥ s k+s-1 v and |S| ≤ s.

Proof. We begin by noting our assumption is that |OPT| ≤ k and g(OPT) ≥ v. If OPT = ∅, then v ≤ f (∅), implying that any solution satisfies the lemma. Therefore, in the following, we assume that OPT = ∅. We now prove by induction, first on k and then on s. In the base case k = 1, as the algorithm chooses an element e maximizing g(e), we have g(e) ≥ g(o 1 ) = g(OPT) ≥ v.

For the induction step k > 1, we apply induction on s. In the base case s = 1, again the algorithm chooses an element e maximizing g(e), so g(e) ≥ g(o 1 ) ≥ g(OPT) k ≥ v k , where the second inequality follows from submodularity. For the induction step s > 1, the algorithm creates two branches. Now consider two possibilities. if k ≥ 2 and s ≥ 2 then 3:

(Branch 1)

4:

Let e be the first element such that g(e) ≥ v k+s-1 .

5:

Define g ′ = g(• | e).

6:

Apply Cardinality(k, s -1, vg(e), g ′ ) on all the elements after e.

7:

Let S ′ be the returned solution.

8:

S 1 := S ′ + e.

9:

(Branch 2)

10:

Apply Cardinality(k -1, s, k+s-2 k+s-1 v, g) on all the elements.

11:

Let S 2 be the returned solution.

12:

if g(S 1 ) > g(S 2 ) then return S 1 .

13:

else return S 2 .

14:

if k = 1 or s = 1 then return arg max e g(e).

apply induction hypothesis on Cardinality(k, s -1, vg(e), g ′ ), which returns a solution S ′ with g

′ (S ′ ) ≥ s-1 k+s-2 v -g(e) and |S ′ | ≤ s -1. Then g(S 1 ) = g ′ (S ′ ) + g(e) ≥ s -1 k + s -2 v + k -1 k + s -2 g(e) ≥ s k + -1 v.
Clearly, |S 1 | ≤ s.

• Suppose that g(o 1 ) < v k+s-1 . Then g(OPTo 1 ) ≥ g(OPT)g(o 1 ) ≥ k+s-2 k+s-1 v, due to submodularity. By the induction hypothesis, Cardinality(k -1, s, k+s-2 k+s-1 v, g) in Branch 2 returns a solution S 2 with g(S 2 ) ≥ s k+s-2 k+s-2

k+s-1 v = s k+s-1 v. Clearly, |S 2 | ≤ s.
Therefore, one of the two branches gives the desired solution. This finishes the induction step on s and then also on k. The proof follows.

Theorem 4.2. Suppose that v ≤ f (OPT). Then,the algorithm Cardinality(K, K, v, f ) returns a solution S with f (S)

≥ K 2K-1 v. The space complexity (for a fixed v) is O K2 2K .
Proof. The first part follows from Lemma 4.1. For space requirement, let Γ(k, s) denotes the space required for Cardinality(k, s, v, g) and let c be some constant. Then it follows from the algorithm that (1) Γ(k, s) ≤ c when k = 1 or s = 1, and (2) Γ(k, s) ≤ Γ(k -1, s) + Γ(k, s -1) + c when k > 1 and s > 1. It is easy to verify this recurrence leads to Γ(k, s) ≤ k2 k+s c. The proof follows.

Therefore, if we are given v such that v ≤ f (OPT) ≤ (1+ε)v, Cardinality(K, K, v, f ) returns a solution S with f (S) ≥ K 2K-1ε f (OPT). Our algorithm consists in invoking Cardinality(K, K, v, f ) for v in some interval, while updating the interval dynamically. See Section 4.3 for details. 1: procedure Matroid(k, v, g, I)

2: if k > 1 then 3: β := max b∈Z + b K 4 ≤ v 2 .
4:

for 0 ≤ b ≤ β do 5:

T := ∅.

6:

while |I ∪ T | < K do

7:

Let e be the first element in the remaining stream satisfying (1) I ∪ T + e ∈ I, and (2) g(e) ≥ bv K 4 .

8:

Branch (b, |T | + 1)

9:

Define g ′ = g(• | e).

10:

Apply Matroid(k -1, (1 -1 K 4 )v -2g(e), g ′ , I + e) on all the elements after e.

11:

Let the returned solution be S ′ .

12:

S b,|T |+1 := e + S ′ .

13:

T := T + e.

14:

Branch 0 15:

S 0 := arg max e,e∈I g(e).

Matroid Constraint

Let M = (E, I) be a given matroid, whose ground set E is the entire stream of elements. Assume that the rank of M is K. We present the procedure Matroid(k, v, g, I) as Algorithm 2. Again g is the submodular function defined over the remaining elements, among which OPT satisfies the conditions that g(OPT) ≥ v and |OPT| = k ≤ K. Moreover, an independent set I ∈ I is also given as a part of the input; such a set I should guarantee that I ∪ OPT ∈ I.

We now give the intuition of this procedure. We guess out possible values of g(o 1 ) in intervals of v K 4 (between 0 and 0.5v). For each possible interval bv K 4 , (b+1)v K 4

of g(o 1 ), we create a branch, and we could potentially take the first element e so that I + e ∈ I, g(e) ≥ bv K 4 , and then define g ′ = g(• | e) and invoke Matroid(k -1, (1 -1 K 4 )v -2g(e), g ′ , I + e) on the elements after e. So far the idea is similar to the previous cardinality case. The problem of this approach is that there is no guarantee that (I + e) ∪ (OPTo 1 ) ∈ I, that is a required condition for the procedure

Matroid(k -1, (1 -1 K 4 )v -2g (
e), g ′ , I + e). To remedy this issue, we introduce the following idea. For each possible interval bv K 4 , (b+1)v The following fact is well-known. Proof. We prove by establishing a more general statement: there is no circuit C * ⊆ I ∪ OPT ∪ T so that C * ∋ o 1 (this implies that the lemma as I ∪ T ∈ I). We proceed by contradiction. Assume that such a circuit C * does exist and we will establish the following claim. In both cases, we know that there exists an element e ∈ T ∪ {o 1 } so that (1) g(e) ≥ bv K 4 , (2) g ′ (OPTe) ≥ 1 -1 K 4 v -2g(e), and (3) (I + e) ∪ (OPTo 1 ) ∈ I. Furthermore, all elements of OPTo 1 are considered by Matroid(k -1, 1 -1 K 4 v -2g(e), g ′ , I + e). Then by induction hypothesis, in Branch(b, j) for some j, we obtain a solution g(S b,j ) ≥ g(e) + 1 -

1 K 4 v -2g(e) 1 2 1 - 1 2K -k + 1 ≥ 1 2 1 - 1 2K -k v.
This finishes the induction step.

The fact that the returned solution S satisfies S ∪ I ∈ I is easy to verify.

Theorem 4.6. Suppose that v ≤ f (OPT). Then the algorithm Matroid(K, v, f, ∅) returns a solution S guaranteeing that f (S) ≥ 1 2 -1 2K v. The space complexity (for a fixed v) is O K 5K+1 .

Proof. The first part follows from Lemma 4.5. For the space complexity, consider the branching tree with Matroid(K, v, f, ∅) as the root. By the algorithm, each node has at most O(K 5 ) branches. Furthermore, the space required for such a node is K + c for some constant c (for each branch, we need to store an element). The depth of such a tree is at most K. So the total complexity is at most O(K 5K+1 ).

Implementation

We now explain how to implement the algorithms described in the preceding sections without knowing the optimal value v. We adapt the dynamic-update technique in [START_REF] Badanidiyuru | Streaming submodular maximization: massive data summarization on the fly[END_REF]. We here explain the cardinality case. The matroid case is analogous. We will let v be a number of the form 1 + ε i for some i ∈ Z. We observe that max e f (e) ≤ f (OPT) ≤ K max e f (e).

Let m be the maximum of f (e) among all elements e that have arrived so far. The algorithm Cardinality(K, K, v, f ) is activated only when m (1+ε) 2 ≤ v ≤ Km ε . The critical observation is that, if f (OPT) > Km ε , then the set of optimal items OPT ′ \ OPT that have arrived so far has the property that

f (OPT ′ ) ≤ o i ∈OPT ′ f (o i ) ≤ Km ≤ εf (OPT).
Therefore, the first time an element e arrives so that m := f (e) and m ≤ f (OPT) ≤ Km ε , there exists a subset OPT = OPT\OPT ′ so that f (OPT) ≥ (1ε)f (OPT). This means that we can use OPT instead of OPT to perform the algorithm. Then the interval m (1+ε) 2 , Km ε contains v such that v ≤ f (OPT) ≤ (1 + ε)v, since m ≤ f (OPT) ≤ Km ε . It follows from Theorem 4.2 that, using O K2 2K space, Cardinality(K, K, v, f ) returns a solution S with f (S) ≥ K 2K-1 v, implying that

f (S) ≥ K 2K -1 (1 -ε)f (OPT) ≥ K 2K -1 (1 -O(ε))f (OPT).
The number of guesses for v is equal to O log 1+ε K ε = O log(K/ε) ε . Theorems 1.4 and 1.5 follow from the preceding discussion and Theorems 4.2 and 4.6.

Theorem 1 . 4 .

 14 There exists a weak-oracle K 2K-1ε -approximation streaming algorithm for monotone submodular function maximization under a cardinality constraint with O K2 2K log(K/ε) ε space.

∆

  r (b, r) is strictly monotonically decreasing in b until b = h + r (we color it differently); when b is 1 To see ∆r(b, r) ≥ ∆r(b + 1, r), it suffices to show when b = h + r and when b

.

  Proof. They follow from the definition of ∆ r . (1) clearly holds when b+ 2 ≤ h + r, because ∆ r is a linear function with respect to b . When b = h + r -1, (1) also holds since 2∆ r (b + 1, r) = 2(K -1r), ∆ r (b, r) = Kr, and ∆ r (b + 2, r) = K -1 -(r + 1). For (2), the equality holds when h + r + 1 ≤ b, since ∆ r depends on b + r. Moreover, when h + r = b, the equality holds since

16 :

 16 return arg max {g(S) | S ∈ {S b,j | b = 0, . . . , β, j = 1, . . . , k} ∪ S 0 }.

K 4 ofg(o 1 )

 41 , we create a set T , initialized as ∅. Every time a new element e arrives so that (1) I ∪T +e ∈ I, and (2) g(e) ≥ bv K 4 , we add e into T and create a new branch Matroid(k-1, (1-1 K 4 )v-2g(e), g ′ , I +e), where g ′ = g(• | e). As we will show (see the proof of Lemma 4.5), at least one of the elements e ∈ T satisfies the property (I + e) ∪ (OPTo 1 ) ∈ I. Apparently, |T | ≤ K, so in total we have at most K + 1 branches for each b.

Proposition 4 . 3 .Lemma 4 . 4 .

 4344 Suppose that C 1 and C 2 are two circuits and x ∈ C 1 ∩ C 2 . Then, for any y ∈ C 1 \C 2 , there exists another circuit C ⊆ C 1 ∪ C 2x and C ∋ y. Let T = e 1 , . . . , e |T | . Suppose that I ∪ T ∈ I and I ∪ OPT ∈ I holds. Furthermore, suppose that for each e i ∈ T , I ∪OPT+e i contains a circuit C i so that C i ∋ o 1 . Then I ∪T +o 1 ∈ I.

Claim 4 .Lemma 4 . 5 .

 445 Suppose that C * ∋ o 1 and C * ⊆ I ∪ OPT ∪ T and C * ∩ T = ∅. Then, there exists another circuit C ⊆ I ∪ OPT ∪ T , C ∋ o 1 and |C ∩ T | < |C * ∩ T |.Proof. To prove the claim, assume that e i ∈ C * ∩ T . Then by Proposition 4.3, we have a circuitC ⊆ C i ∪ C *e i and C ∋ o 1 (recall that C i is the circuit contained in I ∪ OPT + e i and C i ∋ o 1 ). Clearly, |C ∩ T | < |C * ∩ T |.Now by this claim, we conclude that there is a circuit C ⊆ I ∪ OPT and C ∋ o 1 , a contradiction to the assumption that I ∪ OPT ∈ I. Suppose that there is a set OPT in the input stream so that g(OPT) ≥ v, I ∪OPT ∈ I, and |OPT| = k. Then Matroid(k, v, g, I) returns a solution S so that g(S) ≥ 1 2 1 -1 2K-k v and I ∪ S ∈ I.

Proof.

  We prove by induction on k. For the base case k = 1, Branch 0 is bound to get an element e so that g(e) ≥ g(OPT) ≥ v. So assume that k > 1. Then there exists b with 0 ≤ b ≤ β such that bv K 4 ≤ g(o 1 ) ≤ (b+1)v K 4 . Let T = e 1 , . . . , e |T | be the set collected for this b at the moment immediately before o 1 arrives. There are two possibilities.• If some element e i ∈ T satisfies the condition that either I ∪ OPT + e i is independent or contains a circuit C i and C i ∋ o 1 , then I ∪ OPT + e io 1 ∈ I. Moreover, it holds thatg ′ (OPTo 1 ) ≥ g(OPT)g(o 1 )g(e) ≥ 1 -1 K 4 v -2g(e) as g(o 1 ) ≤ g(e) + v K 4 .• Otherwise, that is, if every element e i ∈ T satisfies the condition that I ∪ OPT + e i contains a circuit C i and C i ∋ o 1 , then by Lemma 4.4, I ∪ T + o 1 ∈ I, implying that o 1 will be added into T .

Table 1 :

 1 Summary of results

	Constraint	Approximation ratio Space usage Oracle	Reference
	Algorithm	1 2 -ε	O K ε	weak	[26]
	Cardinality

  s ℓ t and f ℓ t denote the realizations of δ t-1 , d t , s t and f t , based on By the induction hypothesis, f t-1 is monotone, and hence we see

	K j=K-(t-1) {r ℓ j , b ℓ j }.

Here we note that the terms δt-1, dt, and st indeed depend on the value of r K-(t-1) , r K-(t-2) , . . . , rK and b K-(t-1) , b K-(t-2) , . . . , bK . However, we choose to avoid the cumbersome notation of associating the former with the latter.

* Supported by JST ERATO Grant Number JPMJER1201, Japan, and by JSPS KAKENHI Grant Number JP17K00028.

in this case is equal to m t . In addition, it holds that m t is an upped bound of f t , since a t d t is non-negative in [START_REF] Balkanski | The adaptive complexity of maximizing a submodular function[END_REF]. Indeed, a t d t = 0 when d t = 0, and when d t ≥ 1, a t is non-negative since δ t-1 is non-negative by the induction hypothesis. Thus m t is the maximum value of f t , which implies [START_REF] Badanidiyuru | Streaming submodular maximization: massive data summarization on the fly[END_REF].

For [START_REF] Badanidiyuru | Fast algorithms for maximizing submodular functions[END_REF], when r K-(t-1

, the induction hypothesis gives that δ t-1 = m t-1 . Since s t = 1 and d t = 2(t -1) when r K-(t-1) = b K-(t-1) = 0, it holds that a t d t = m t-1 (2s t + d t -1)d t = m t-1 (2t -1)(2t -2) = (2t -1)!, which is exactly m t . Thus f t (0, . . . , 0; 0, . . . , 0) = 0 by [START_REF] Balkanski | The adaptive complexity of maximizing a submodular function[END_REF]. Since f t is monotone by [START_REF] Alon | Optimizing budget allocation among channels and influencers[END_REF], it is minimum.

Therefore, (1)-( 3) hold.

We calculate the function value obtained by an algorithm (Lemma 3.1 (iii)).

Lemma 3.5. For any t = 1, 2, . . . , K, the constructed function f t satisfies the following.

Proof. We prove by induction on t. When t = 1, it is straightforward to verify the lemma. By the induction hypothesis, f t-1 (0, . . . , 0, 1; 1, . . . ,

As s t = 1 and d t = 2t -3, it holds by ( 5) that

where the last equality is easy to verify.

We next deal with submodularity of the constructed function.

Lemma 3.6. For any t = 1, 2, . . . , K, the constructed function f t satisfies the following: Suppose that

For any integer

Proof. We proceed by induction on t. The base case t = 1 is easy to verify. For the induction step where t ≥ 2, let d ℓ t , s ℓ t and δ ℓ t-1 denote the realizations of d t , s t , and

, and thus

Then it follows from (5) that the left-hand side of ( 7) is equal to

Similarly, the right-hand side of ( 7) is equal to

Since We are left with proving indistinguishability. We begin by proving that when only elements of a particular class are present, the f t -values are entirely determined by their cardinality. Lemma 3.7. For any t = 2, 3, . . . , K and any non-negative integer b, it holds that f t (1, 0, . . . , 0; b, 0, . . . , 0) = f t (0, 0, . . . , 0; b + 1, 0, . . . , 0).

Proof. Let d 1

t and d 2 t , δ 1 t-1 and δ 2 t-1 be the realizations of d t and δ t-1 based on (1, 0, . . . , 0; b, 0, . . . , 0) and (0, 0, . . . , 0; b + 1, 0, . . . , 0), respectively. Then δ 1 t-1 = δ 2 t-1 = m t-1 holds by Lemma 3.4. By (5), the two function values stated in the lemma can be written as

respectively. If b ≥ 2(t -1), then both d 1 t and d 2 t are 0, which gives the equivalence of the two above expressions. So assume that b + 1 ≤ 2(t -1), and hence d 1 t = d 2 t + 1. Then, since

the above two expressions are equivalent. The proof follows.

The next lemma generalizes the previous one: if we fix the numbers of red and blue elements of classes before class i, then the function value is entirely determined by the cardinality of elements in class i. This proves Lemma 3.1 (iv) by setting t = K. Lemma 3.8. For any i = 2, 3, . . . , K and any integer t such that Ki + 1 ≤ t ≤ K, it holds that f t (r K-(t-1) , . . . , r i+1 , 1, 0, . . . , 0; b K-(t-1) , . . . , b i+1 , b i , 0, . . . , 0) = f t (r K-(t-1) , . . . , r i+1 , 0, 0, . . . , 0; b K-(t-1) , . . . , b i+1 , b i + 1, 0, . . . , 0).

Proof. We prove by induction on t. The base case t = Ki + 1 follows from Lemma 3.7. For the induction step when t > Ki + 1, let δ ℓ t-1 be the realization of δ t-1 based on i j=K-(t-2) {r ℓ j , b ℓ j } for ℓ = 1, 2. Induction hypothesis then states that δ 1 t-1 = δ 2 t-1 and the proof follows by observing how the function is defined by recurrence (5). Lemma 3.1 follows from Lemmas 3.4, 3.5, 3.6, and 3.8.

Proof of Observations in Section 3.2

We first prove Lemma 3.2.

Proof of Lemma 3.2. Let t be an integer from 2 to K. We first compute f t (1, 0, . . . , 0; 0, . . . , 0). By Lemma 3.4, f t-1 (0, . . . , 0; 0, . . . , 0) = 0 and hence δ t-1 = m t-1 . Hence, since s t = 0 and

On the other hand, since s t = 1 and d t = 2(t -1) -1 in the case of f t (0, . . . , 0; 1, 0, . . . , 0),

Suppose that we are given r K-(t-1) , r K-(t-2) , . . . , r K and b

Similarly, we have f (0, . . . , 0; 0, . . . , 0, 1, 0, . . . , 0) = 2 • (2K -2)!. Moreover, since f 1 (1; 0) = 1 by the definition, it holds that f (0, . . . , 0, 1; 0, . . . ,

Thus Lemma 3.2 holds.

Below we prove Lemma 3.3. Lemma 3.3. It follows from Lemma 3.4 that f (1, . . . , 1; 0, . . . , 0) = f K (1, . . . , 1; 0, . . . , 0) = (2K -1)!.

Moreover, Lemma 3.3 imlplies that f (1, 0, . . . , 0; 0, . . . , 0) + f (0, 1, . . . , 0; 0, . . . , 0) + • • • + f (0, . . . , 0, 1; 0, . . . , 0)

Thus the first equality holds.

We next consider computing f (0, . . . , 0; 2(K -1), 0, . . . , 0). Since f K-1 (0, . . . , 0; 0, . . . , 0) = 0, we have δ K-1 = m K-1 . Hence, since s K = 1 and d K = 0 in this case, we see from (5) that

Thus Lemma 3.3 follows.

Algorithms

In this section, we present algorithms for a cardinality constraint and a matroid constraint, respectively.

We first establish some convention here. We call the input problem the original instance, in which all elements in the stream are considered. Furthermore,

• K denotes the size constraint for the input cardinality constraint or the rank of the input matroid;

• OPT is the optimal solution of the original instance;

• f : 2 E → Z + is the input submodular function.

All algorithms are given in the form of a general procedure with a set of parameters (in particular, a re-defined submodular function and a modified cardinality/matroid constraint). Each invocation of the general procedure is called a branch. A branch considers all remaining elements that have not arrived so far (i.e., a suffix of the entire stream of elements). For a branch, we use the following notation.

• k denotes the size constraint for a new cardinality constraint or the rank of the new matroid (as a rule k ≤ K);

• OPT is the intersection of OPT and the remaining elements considered by this branch;

• g is a submodular function derived from f . More specifically, g(T ) = f (T | S) := f (T ∪ S)f (S), where S is a subset of elements that have already arrived so far before this branch starts.