Improved Algorithms for Maximum Coverage
in Dynamic and Random Order Streams

To establish our new results, we revisit recent work on the maximum coverage problem in the relevant data stream models and show how to refine and extend the approaches to substantially decrease the the amount of space needed to solve the problem in the data stream model. In the process, we also establish secondary results on speeding up the existing algorithms and in one case, developing a slightly more pass efficient algorithm.

In the dynamic stream model, our main result is the following.

This result reappears as Theorem 4.2. It is an improvement over the best previous algorithm by Assadi and Khanna [AK18] that used $(n+\varepsilon^{-4}k)\operatorname{polylog}(n,m)$ space. The high-level approach is similar and is based on the existing $\ell_{0}$ sampling primitive that allows uniform sampling amongst the sets that are inserted but not deleted. In each pass, we pick additional sets and maintain the union $C$ of the selected sets. We pick the additional sets by sampling only among the sets that include a “meaningful” number of elements that are not currently in $C$. Unfortunately, when we simultaneously sample multiple sets in this way, once we start adding sampled sets to our solution, some of the sampled sets may no longer make a meaningful increment to $|C|$. However, by repeating the process over multiple passes, with a slowly decreasing threshold for what constitutes a meaningful improvement, we ensure that either we exhaust the collection of sets that could potentially be worth adding or we add enough sets and together these yield a good approximate solution. The main point of departure from Assadi and Khanna [AK18] is in the way we handle the decreasing threshold. The largest threshold considered by Assadi and Khanna is about $\operatorname{OPT}/k$; this is sufficient for achieving a $1-1/e-\varepsilon$ approximation factor, but has the downside that there can be many overlapping sets that would contribute more than $\operatorname{OPT}/k$ new elements to $C$; storing these sets during the sampling process is expensive. Instead, we consider thresholds decreasing from $\operatorname{OPT}$ but handling the sets that make a contribution between $\operatorname{OPT}/2^{i}$ and $\operatorname{OPT}/2^{i+1}$ for $i=0,\ldots,\log k$ separately but in parallel. We analyze a stochastic process—we call it the cascading urns process—to show how our new algorithm uses a similar number of passes as the algorithm by Assadi and Khanna [AK18] but uses significantly less space. We present the details in Section 4. In fact, a more careful analysis of the process shows that it is possible to reduce the number of passes to $O(\log m+\varepsilon^{-1}\log m/\log\log m)$ in contrast to the $O(\varepsilon^{-1}\log m)$ passes used by previous algorithm. We believe that a similar pass saving can be achieved in Assadi and Khanna [AK18] but it requires an extra log factor in the space.

In the random order model, our main result is the following.

The above result is established in Section 5.2. Note that the dependence on $\varepsilon$ in the result is exponential and this makes the algorithm less practical. The main significance of the result is removing a factor $k$ in the space required by the best previous result, by Warneke et al. [WCW23], that used $\varepsilon^{-2}k^{2}\operatorname{polylog}(n,m)$ space. Both their and our approach are based on modifying existing algorithms for the cardinality constrained monotone submodular optimization problem. This is a more general problem than maximum coverage, but it is assumed in the general problem that the algorithm has oracle access to the function being optimized. For maximum coverage, we need to store enough information to be able to simulate this oracle. An $O_{\varepsilon}(k^{2}\log m)$-space algorithm for maximum coverage follows immediately for any $O_{\varepsilon}(k)$ space algorithm for monotone submodular optimization because the universe subsampling technique discussed in Section 3 allows us to focus on the case where set has size $O(\varepsilon^{-2}k\log m)$. To reduce the dependence on $k$ to linear, rather than quadratic, we need a more careful adaption of an algorithm by Agrawal et al. [ASS19]. We maintain a set of size $O(\varepsilon^{-2}k\log m)$ corresponding to the items covered by a collection of sets chosen for the solution so far, along with $O_{\varepsilon}(1)$ sets of size $O_{\varepsilon}(\log m)$. We mention in passing that, being a thresholding algorithm, salsa is easy to adapt to our $O_{\varepsilon}(k\cdot\operatorname{polylog}(n,m))$ regime, yielding an approximation factor of $1/2+c_{0}$. We present the details in Section 5.

Lastly, our results, along with numerous previous results, use the aforementioned universe sub-sampling technique introduced by McGregor and Vu [MV19a] to sparsify the input instance. We explain how this technique and others used in the paper can be implemented such that the amortized update time of our algorithm is polylogarithmic. This also implies an improvement of the state-of-the-art insert only algorithms in terms of the update time: $\operatorname{polylog}(m,n)$ update time suffices whereas the best previous result by Jaud et al. [JWC23] required update time $k\cdot\operatorname{polylog}(m,n)$. We present the details in Section 6.

An urn contains $m$ balls, each initially gold. Balls are drawn from the urn in phases, where a phase consists of drawing $d$ balls uniformly at random, with replacement. When a ball is drawn, if it is gold, then we earn one point and some arbitrary subset of the balls in the urn turn into lead, including the ball that was just drawn (and put back). At the end of the phase, all lead balls are removed from the urn and the next phase begins. The process ends when either $d$ points have been earned or the urn is empty.

We will prove the following result about this process.

The intuition behind the result is as follow. The observation is that if the fraction of balls in the urn remains above $d^{\prime}/d$ then each draw is gold with probability at least $d^{\prime}/d$ and it would be reasonable to expect at least $d^{\prime}/d\times d=d^{\prime}$ of the draws to be gold. Define $m(i)$ to be number of gold balls left in the urn after $i-1$ rounds and let $d(i)$ be the number of gold balls observed in the $i$-th round. For the sake of intuition (the formal proof follows shortly) suppose the observation holds for all rounds even though $d(i)$ and $m(i+1)$ are dependent, i.e., $m(i+1)/m(i)\leq d(i)/d$ for all $i$; then

by the AM-GM inequality and the fact that every drawn gold ball is turned into lead, so only contributes to at most one term $d(j)$, hence $(\sum_{j}d(j)/d)\leq 1$. Consequently, $i$ can be at most $O(\log m/\log\log m)$ before $m(i+1)$ becomes zero.

Our result is stronger than analogous results in previous work in two specific ways. Previous analyses essentially need a) an factor $O(\log m)$ in the number of draws taken in each phase and b) only establish that $O(\log m)$ phases suffice, rather than $O(\log m/\log\log m)$ phases. The improvements in our approach stem from avoiding the need to guarantee that each phase makes progress with high probability and considering both the progress made towards observing $d$ gold balls and the progress made in terms of turning balls into lead.

We turn to lower bounding the success probability of a phase as claimed in the above proof. Fix a particular phase and a particular realization of all previous phases of the stochastic process. Let $G_{i}$ be the event that the $i$th draw of this phase reveals a gold ball (and thus earns a point); let $L_{i}$ be the event that after $i-1$ draws, the fraction of gold balls in the urn is less than $\gamma$. Define indicator variables $X_{i}=\mathbbm{1}_{G_{i}\cup L_{i}}$ and put $X=\sum_{i=1}^{d}X_{i}$. Then,

Finally, we show that $X$ stochastically dominates a binomial random variable, which then lower-bounds $\Pr[X\geq\gamma d/2]$. Denote Bernoulli and binomial distributions as “Bern” and “Bin.”

To prove the first part of Lemma 4.1, we will also need to analyze a more complex version of the above process; we call it the cascading urn process. Now we have $t$ urns, numbered $1$ through $t$, with the $r$th urn starting out with $m_{r}$ balls; let $m=\sum_{r\in[t]}m_{r}$. Drawing a gold ball from urn $r$ is worth $d/2^{r}$ points. Initially, all balls are gold. The process works as follows.

• •

  Balls are drawn in phases: a phase consists of drawing $2^{r}$ balls from urn $r$, in order of increasing $r$.

• •

  When a ball is drawn from urn $r$, if it is gold, the following things happen: (i) it turns into lead and is returned to urn $r$; (ii) some arbitrary subset of the balls in the urns (all urns, not just urn $r$) turn into lead; and (iii) we earn $d/2^{r}$ points.

• •

  At the end of each phase, each lead ball in an urn is removed from its current urn and either destroyed or transformed back into gold and placed in a higher-numbered urn. We then start the next phase with all balls being gold again.

The process ends when either $d$ points have been earned or all urns have become empty.

We now circle back to Algorithm 1. To finish its analysis, we need to prove Lemma 4.1, which we can now do, as an application of what we have established about these urn processes.

To analyze the while loop at 1, apply Theorem 4.6 with $t=\left\lfloor\log k\right\rfloor$ as follows. The balls in the $i$th urn correspond to the sets in $\mathcal{F}_{i}^{C}$. A ball is gold if the corresponding set $S$ satisfies $|S\setminus C|\geq\theta_{i}$; otherwise, it is lead. Adding a set $S$ to the candidate solution $Y$ grows the set $C$ of covered elements, thereby turning gold balls to lead in some complicated way that the algorithm cannot easily track. The bound on the number of phases until the urn process terminates translates to a bound of $O(\log k+\log m)$ on the number of iterations of that while loop. Noting that $k\leq m$ gives Lemma 4.1.

Similarly, Theorem 4.3 implies that the number of iterations of the while loop at 2 is $O(\log m/\log\log m)$. This completes the analysis.

To motivate the approach, consider a variant of the problem in which an algorithm is presented with a random permutation of the input sets, but we make the following two changes:

1. 1.

   For a fixed optimal solution consisting of sets $O_{1},\ldots,O_{k}$, replace the occurrences of these sets in the stream by a set drawn uniformly at random from $\{O_{1},\ldots,O_{k}\}$.

2. 2.

   We give the algorithm foreknowledge of a way to segment the stream into $k$ contiguous sub-streams $\mathcal{C}_{1},\ldots,\mathcal{C}_{k}$ such that each contains exactly one element from $\{O_{1},\ldots,O_{k}\}$.

Then consider the greedy algorithm that outputs the sequence $\langle S_{1},\ldots,S_{k}\rangle$ where

To analyze this algorithm, define

and note that

since for all $j\in[k]$,

Note also that

Hence,

The space required to implement this algorithm is $O(k\varepsilon^{-2}\log m)$ since it suffices to maintain the union of the sets chosen thus far rather than the sets themselves.

To handle the original random order setting, we obviously need to deal with the fact that the algorithm does not have foreknowledge of a segmentation of the stream such that each segment contains exactly one set from the optimum solution. A naive approach would be to segment the stream into $\beta k$ contiguous segments for some large constant $\beta>0$ with the hope that few pairs of optimum sets appear in the same segment. We could then consider all $\binom{\beta k}{k}=e^{O(k)}$ subsequences of these segments but this is clearly inefficient. A better approach is to use limited number of guesses in parallel using an approach by Agrawal et al. [ASS19]. More complicated to analyze, especially when combined with the goal of using limited space, is the fact that because the $O$-sets appear randomly permuted, rather than independently sampled, there are now various dependencies to contend with.

We will randomly partition the input collection $\mathcal{C}$ of sets into $k\beta$ groups $\mathcal{C}_{1},\ldots,\mathcal{C}_{k\beta}$. These groups will ultimately correspond to segments of the stream, i.e., the first $|\mathcal{C}_{1}|\sim Bin(m,1/(k\beta))$ sets define $\mathcal{C}_{1}$ etc. For any

we define a sequence of groups

At the heart of the algorithm is a greedy process run on such sequences. For $\mathcal{I}=\{i_{1},i_{2},\ldots\}\in\{1,\ldots,k\beta\}$, $C\subset[n]$, and a “reserve” collection of sets, $\mathcal{R}$—the name will become clear later—define the greedy sequence:

where

Algorithm 2 contains most details, but to fully specify the algorithm, we need to define the original groups $\mathcal{C}_{1},\mathcal{C}_{2},\ldots,\mathcal{C}_{k\beta}$. To do this, for each set $S$ define a random variable $Y_{S}$ that is uniform over $\{1,2,\ldots,k\beta\}$. Then, we define $\mathcal{C}_{i}=\{S:Y_{S}=i\}$. Equivalently, for a random permutation of the stream $\mathcal{C}_{1}$ is the first $|\{S:Y_{S}=1\}|$ sets in the stream, $\mathcal{C}_{2}$ is the next $|\{S:Y_{S}=2\}|$ sets in the stream, etc. Given this definition of the stream, Algorithm 2 maintains sets whose total size is

where the first term corresponds to maintaining $C$, the next term consists of all sets appearing in greedy subsequences during the processing of each window (defined in line 2 of Algorithm 2), and the last term corresponds to storing sets in $\mathcal{R}$. For sets $S$ in $\mathcal{R}$ it suffices to store $S\setminus C$ rather than $S$ itself. Hence, the total number of elements in sets in $\mathcal{R}$ is at most $|\mathcal{R}|\operatorname{OPT}/k$.

The motivation for how to set $\alpha$ and $\beta$ is as follows. Let ${\mathcal{O}}=\{O_{1},\ldots,O_{k}\}$ be an optimum collection of $k$ sets. We say a group $\mathcal{C}_{i}$ is active if it contains a set from ${\mathcal{O}}$ and note if $\beta$ is large enough the number of active groups $\kappa$ is close to $k$. Furthermore, in each window the number of active groups is expected to be $\kappa\cdot(\alpha\beta)/(k\beta)=\alpha\kappa/k\approx\alpha$. We will later set $\alpha$ to be large enough such that the number of active groups in each window is typically close to $\alpha$, i.e., there is an $\alpha$-length subsequence of the window that mainly consists of active groups.