Unit Interval Selection in Random Order Streams

We make use of an established technique that, given a one-pass streaming algorithm for unit-length intervals that are all contained in the restricted domain $[0,\mathrm{\Delta })$, for some constant integer $\mathrm{\Delta }$, and has approximation factor $\alpha$, produces an algorithm for unrestricted domains with only a constant factor blow-up in space and a factor $(\mathrm{\Delta }-1)/\mathrm{\Delta }$ blow-up in the approximation factor [11]. We thus see that it is enough to design an algorithm for the restricted domain $[0,\mathrm{\Delta })$, for some large but constant $\mathrm{\Delta }$, large enough so as to minimize the impact of the factor $(\mathrm{\Delta }-1)/\mathrm{\Delta }$ on the final approximation factor.

To this end, as a key building block of our algorithm, we employ the following strategy: We maintain the left-most interval $I_L$ observed thus far in the stream, and feed the substream of intervals that lie to the right of $I_L$ into a recursive instance of our algorithm. This building block then returns the interval $I_L$ together with the solution produced by the recursive call. To see the strength of this method, denote by $OPT$ an arbitrary but fixed optimal solution. Furthermore, assume that the left-most interval $op{t}_1\in OPT$ arrives before any of the other intervals in $OPT$. In this case, the algorithm would have either picked $op{t}_1$ as the interval $I_L$ or an interval that is even further left as $op{t}_1$, and the substream fed into the recursive call of the algorithm contains $OPT\setminus op{t}_1$, i.e., an independent set that is only by one smaller. In other words, the algorithm has acted optimally thus far since one interval $I_L$ was selected and a subinstance that contains an independent set of size $|OPT|-1$ was created whose solution can be combined with the selected interval $I_L$.

Unfortunately, the event that $op{t}_1$ appears first among the intervals of $OPT$ has a probability of only $1/|OPT|$ (over the random order of the stream). Our aim, however, is to make this approach work, even if any other interval of $OPT$ is the first to arrive among the intervals in $OPT$. First, by symmetry, we see that the approach above also works when the right-most interval of $OPT$ arrives first. Hence, suppose now that the $i$-th (counted from left to right) optimal interval $op{t}_i\in OPT$ arrives before any of the other optimal intervals, for some . Furthermore, let $\mathrm{\ell }$ be the largest integer strictly smaller than the left boundary of $op{t}_i$, and let $r$ be the smallest integer strictly larger than the right boundary of $op{t}_i$. Then, we construct two solutions and pick the larger one, as follows. For solution 1, we combine the outputs of two independent runs of our algorithm, one on the domain $[0,\mathrm{\ell })$, and one on the domain $[\mathrm{\ell },\mathrm{\Delta })$. While these runs ignore intervals that intersect with the point $\mathrm{\ell }$ and may thus potentially miss a crucial optimal interval that intersects this point, we can now exploit the fact that the interval $op{t}_i$ is the left-most optimal interval in the domain $[\mathrm{\ell },\mathrm{\Delta })$. Hence, as discussed above, the run on $[\mathrm{\ell },\mathrm{\Delta })$ does not make any mistake when selecting the interval $op{t}_i$ as the leftmost interval (or an interval within $[\mathrm{\ell },\mathrm{\Delta })$ that lies even further to the left as $op{t}_i$) into the final solution. For solution 2, we combine the outputs of the two runs of the algorithm on the domains $[0,r)$, and $[r,\mathrm{\Delta })$, respectively, and now exploit the fact that $op{t}_i$ is the right-most optimal interval in the domain $[0,r)$.

Last, since our algorithm cannot know which interval of $OPT$ will indeed arrive first, we run the above strategy for every integer $1\le i\le |OPT|$. We observe that this still yields an algorithm with only constant space complexity since the domain $[0,\mathrm{\Delta })$ is of constant size, which further implies that the optimal solution within this domain is also only of constant size $|OPT|\le \mathrm{\Delta }-1$.

In our analysis, we establish the monotonicity property that adding intervals to the input stream never decreases the size of the output produced by the algorithm. In other words, the worst-case performance of our algorithm is achieved when the algorithm is run on an independent set – a special case that could of course be solved optimally by just reporting these intervals. We can thus focus on analysing the performance of the algorithm on this special case. Due to the many recursive calls of the algorithm, we obtain a recursive formula for the solution size obtained. We observe that the approximation factor $\alpha$ of our algorithm decreases as $\mathrm{\Delta }$ increases. Recall, however, that we still need to apply the technique mentioned above to go from the restricted domain $[0,\mathrm{\Delta })$ to an unrestricted domain, which incurs a further loss in the approximation factor by a factor of $(\mathrm{\Delta }-1)/\mathrm{\Delta }$. Using a computer programme, we see that, for $\mathrm{\Delta }=5000$, the final algorithm has an approximation factor of at least $0.7401$, which is provably very close to the best possible choice. This specific choice of $\mathrm{\Delta }$ is discussed in more detail in the full version of this paper.

Our lower bound is obtained via a reduction to the ${\text{INDEX}}_t$ problem in the one-way two-party communication complexity setting, by combining the clique gadgets already used in [12] and [7] for adversarial order lower bounds with the random order lower bound ideas by Cormode et al. [8].

In the ${\text{INDEX}}_t$ problem, there are two players, denoted Alice and Bob. Alice holds a vector $X\in {\{0,1\}}^t$ consisting of $t$ uniform independent random bits, and Bob is given a uniform random index $A\in [t]$. Alice sends a message to Bob and Bob outputs the bit $X[A]$. The objective is to obtain a communication protocol that communicates a message of smallest possible size. It is known that ${\text{INDEX}}_t$ requires a message of size $\mathrm{\Omega }(t)$. Since streaming algorithms can be used as one-way two-party communication protocols (Alice runs the streaming algorithm on her part of the input and sends the memory state to Bob, who then completes the execution of the algorithm on his part), lower bounds on the message size translate and yield lower bounds on the space used by streaming algorithms.

The ${\text{INDEX}}_t$ problem can be reduced to Unit Interval Selection as follows. Using the bits in $X\in {\{0,1\}}^t$, Alice constructs a clique of $t$ mutually overlapping intervals, i.e., a stack of intervals such that, for every $i>1$, the $i$-th interval is slightly further to the right than the $(i-1)$-th interval. The bits $X[i]$ are encoded in this construction in that, depending on the value of $X[i]$, the $i$-th interval is ever so slightly moved, which, however, does not affect the logic behind the construction. Crucially, an algorithm that outputs the $j$-th interval of the clique stack, for any $j$, must know the value $X[j]$. Then, based on the index $A$, Bob constructs two wing intervals, which surround, but are independent of, the interval corresponding to $X[A]$. The key property is that every clique interval, other than the one corresponding to $X[A]$, must intersect exactly one of these wing intervals, or, in other words, the only independent set of size $3$ consists of the wing intervals together with the $A$-th interval of the stack. This in turn implies that any algorithm on this construction that computes a better than $2/3$-approximation must report the interval corresponding to $X[A]$, and its location allows recovering the bit $X[A]$.

When bringing this construction into the random-order setting, for the resulting construction to be hard it is necessary that the two wing intervals appear after the $A$-th clique interval since otherwise the positions of the wing intervals reveal the index $A$ and an algorithm could then simply collect the $A$-th clique interval when it arrives, obtain an optimal solution to the interval selection problem, and solve the underlying ${\text{INDEX}}_t$ instance. We, however, observe that, under a uniform random arrival order, with probability $1/3$, the two wing intervals indeed arrive after the $A$-th clique interval, and we prove that this case indeed remains hard to solve. Our expected approximation factor lower bound of $8/9$ is then explained by the fact that, with probability $1/3$, an algorithm can only obtain a solution of size $2$, and with probability $2/3$, an algorithm can obtain a solution of optimal size $3$, which results in an expected solution size $1/3\cdot 2+2/3\cdot 3=8/3$, or an approximation factor of $(8/3)/3=8/9$.

On a technical level, our approach is a reduction via the use of shared public randomness in the spirit of the argument from [8]. Alice and Bob sample a shared random permutation of the intervals that are used in the hard instance. Alice constructs each clique interval which arrives before a wing interval via the bits in $X$, and then Bob constructs the wing intervals via $A$, and also the remaining clique intervals via sampling public random variables. This results in a construction that reflects the bit $X[A]$ of the input to ${\text{INDEX}}_t$ precisely when the interval corresponding to $X[A]$ arrives before either wing interval, and this occurs with probability $1/3$, as desired, which yields our lower bound results.

Our proof is via induction over the quantity $b-a$. We first show that the recursion tree will always have finite size.

Each recursive subproblem is instantiated before any intervals arrive. Thus, the size of the recursion tree depends only on $b-a$ and not on the input stream. Each recursive instance has a domain that is by one smaller than the domain of its parent, and an instance with domain size at most 1 creates no subproblems. $\mathrm{⊲}$

We now proceed with the induction.

Suppose $𝒜$ is an instance of Algorithm 1 such that $b-a=1$. Then $|OUT(𝒜({𝒮}^{\prime }))|\le |OUT(𝒜(𝒮))|$.

If $b-a=1$, then no unit length intervals fit within $[a,b)$. Therefore, $𝒮$ and ${𝒮}^{\prime }$ must both be empty streams, and so $|OUT(𝒜({𝒮}^{\prime }))|=|OUT(𝒜(𝒮))|=0$. $◀$

Suppose the lemma holds for all instances of $𝒜$ such that $b-a\le k-1$.

We now consider when $b-a=k$.

By construction, the output of $𝒜$ is formed by combining the outputs of its recursive children, together with either $L_i$ or $R_i$, for some $i$. We will first argue that if any $L_i$ or $R_i$ stores an interval under ${𝒮}^{\prime }$, then it must also store an interval under $𝒮$. We will then argue that all of the recursive children must output solutions at least as large under $𝒮$ compared to ${𝒮}^{\prime }$. This is sufficient to prove the claim.

First, W.L.O.G., suppose some $L_i$ is non-empty under ${𝒮}^{\prime }$. Then, there must exist some interval in ${𝒮}^{\prime }$ which is contained in the domain $[a,i)$. Then, this same interval must also be contained in $𝒮$ ($𝒮$ is a superstream of ${𝒮}^{\prime }$), and so $L_i$ must also be non-empty under $𝒮$. This argument holds for all relevant integers $i$, and also for each $R_i$.

We now turn to the substreams fed into the recursive children of $𝒜$, and begin with the instances ${𝒯}_i^L$ and ${𝒯}_i^R$. W.L.O.G. consider ${𝒯}_i^L$ for some relevant integer $i$. Then, by construction, the size of the domain of ${𝒯}_i^L$ is at most $k-1$. Next, let ${𝒮}_i^{\prime }$ denote the substream of intervals fed into ${𝒯}_i^L$ when ${𝒮}^{\prime }$ is fed into $𝒜$, and ${𝒮}_i$ the substream fed in when $𝒮$ is fed into $𝒜$. Then, ${𝒮}_i^{\prime }$ is precisely the substream of intervals in ${𝒮}^{\prime }$ that are fully contained in $[a,i)$. Then, every interval in ${𝒮}_i^{\prime }$ is also contained in ${𝒮}^{\prime }$ and so $𝒮$, and therefore every interval in ${𝒮}_i^{\prime }$ is also contained in ${𝒮}_i$. This gives us that ${𝒮}_i^{\prime }$ is a substream of ${𝒮}_i$. We can now apply the inductive hypothesis to obtain

The same argument applies for every relevant integer $i$, and also for each ${𝒯}_i^R$.

Finally, we now consider the instances ${𝒜}_i^L$ and ${𝒜}_i^R$. W.L.O.G. consider ${𝒜}_i^L$ for some relevant integer $i$. Then, by construction, the size of the domain of ${𝒜}_i^L$ is at most $k-1$. Next, let ${𝒮}_i^{\prime }$ denote the substream of intervals fed into ${𝒜}_i^L$ when ${𝒮}^{\prime }$ is fed into $𝒜$, and ${𝒮}_i$ the substream fed in when $𝒮$ is fed into $𝒜$. Then, these are each the substreams of ${𝒮}^{\prime }$ and $𝒮$ of the intervals fully contained in $[a,i)$, which are also further left and independent of $L_i$ at the time each interval arrives. We now observe that whenever an interval in ${𝒮}_i^{\prime }$ arrives in $𝒮$, the interval stored in $L_i$ must be at least as far right as when the same interval arrives in ${𝒮}^{\prime }$ - by the construction of the algorithm. Therefore, every interval in ${𝒮}_i^{\prime }$ is also contained in ${𝒮}_i$, giving us that ${𝒮}_i^{\prime }$ is a substream of ${𝒮}_i$. We can now apply the inductive hypothesis to obtain

The same argument applies for every relevant integer $i$, and also for each ${𝒜}_i^R$.

This concludes the proof of the Lemma. $◀$

For a permutation $S_{ℐ}$ of the intervals $ℐ$, we denote by $OPT(S_{ℐ})$ the substream of optimal intervals. Then, since $OPT(S_{ℐ})$ is a substream of $S_{ℐ}$, we can use Lemma 5 to obtain:

The result then follows from the observation that $S_{OPT}$ and $OPT(S_{ℐ})$ are identically distributed. $◀$

We will thus assume from now on that the input instance $ℐ$ is a collection of disjoint intervals. We then take the input stream to be $𝒮\sim \mathrm{\Pi }(I)$ for the remainder of this subsection, and omit writing that $𝒮$ is the input to $𝒜$.

In the following, we will establish lower bounds on $out(x)$, for every $x\ge 0$. To this purpose, we treat the cases $x\in \{0,1,2\}$ explicitly, and then provide a recurrence relation for larger values of $x$.

First, $\alpha =0$ implies the input stream has no intervals, which is trivial. Next, if $\alpha =1$, then the input stream consists of a single interval. This interval will be picked up by $R_1$ since $R_1$ constitutes the left-most interval in the domain $[0,\mathrm{\Delta })$.

Now suppose that $\alpha =2$, which implies that the input consists of two intervals $op{t}_1$ and $op{t}_2$ with $op{t}_1$ further left of $op{t}_2$. If $op{t}_1$ arrives before $op{t}_2$, then $R_1$ will store $op{t}_1$, and $op{t}_2$ will be fed into ${𝒜}_1^R$ and returned by this recursive call. The interval $op{t}_2$ will then be stored as the right most interval fed into ${𝒜}_1^R$, ensuring that $|OUT({𝒜}_1^R)|\ge 1$. We thus obtain that $|R_0\cup OUT({𝒜}_0^R)|=2$. Then, by the construction of the algorithm, we get

Similarly, if $I_2$ arrives first then $L_{\mathrm{\Delta }+1}$ and the output of ${𝒜}_{\mathrm{\Delta }+1}^L$ constitutes a candidate solution of size $2$. $◀$

Next, we consider the case $\alpha \ge 3$. We write

to denote the optimal intervals ordered from left to right, and consider the cases for which interval from $OPT$ arrives first. We then fix some $i\in \{1,\mathrm{\dots },\alpha \}$, and suppose that $op{t}_i$ arrives in the input stream before any other interval in $OPT$. Let $op{t}_i=[f,f+1]$, for some real $f$, and let

denote the smallest integer larger than $f+1$ that does not intersect with $op{t}_i$, and the largest integer smaller than or equal to $f$ which may only intersect with $op{t}_i$’s left endpoint, respectively. Note that when $f$ is an integer, we have $l=f$, but $r=f+2$. This choice is due to the fact that every recursive instantiation of our algorithm is run on a domain with a closed left endpoint and an open right endpoint.

We only prove 1) – the proof of 2) is similar and omitted.

By definition, the interval $op{t}_i$ is further right and independent of $l$, and so will be stored in $R_l$. Next, observe that each of the intervals $op{t}_{i+1},\mathrm{\dots },op{t}_{\alpha }$ are fed into ${𝒜}_l^R$ in uniform random-order. Then, by definition of $out(.)$, we obtain $𝔼|OUT({𝒜}_l^R)|\ge out(\alpha -i)$. Finally, combining $R_l$ and ${𝒜}_R^l$ via linearity of expectation yields the desired bound.

$◀$

The next lemma follows by a similar proof.

We only prove 2) – the proof of 1) is similar and omitted.

By construction, the substream ${𝒮}^{\prime }$ fed into ${𝒯}_l^L$ consists of the intervals in $\{op{t}_1,\mathrm{\dots },op{t}_{i-1}\}$ that do not overlap with the point $l$. Then, since each interval is of unit length, and also $f-l\le 1$ holds, ${𝒮}^{\prime }$ contains either the $i-1$ or $i-2$ left-most intervals of $OPT$, and these are fed into ${𝒯}_l^L$ in a uniform random order. We thus obtain $𝔼|OUT({𝒯}_l^L)|\ge \min \{out(i-1),out(i-2)\}$. Finally, by Lemma 5, $out(\cdot )$ is a non-decreasing function, which implies that $out(i-1)\ge out(i-2)$ holds, and completes the proof. $◀$

We now combine these lemmas to form a recurrence for $out(\cdot )$. In the following, for convenience, we write the maximum function over multiple lines.

The proof follows almost immediately from Lemmas 9 and 10:

$◀$

In the following lemma, we obtain a bound on the expected approximation factor of our algorithm.

Let $\alpha \in \{1,\mathrm{\dots },\mathrm{\Delta }-1\}$ and consider an input instance $ℐ$ that establishes the minimum in the definition of $out(\alpha )$. We consider a run of $𝒜$ on $ℐ$. Then:

In particular, this gives us a recurrence relation for $out(\cdot )$, which we will later use to compute values numerically. The expected approximation factor is then simply this quantity multiplied by $1/\alpha$.

Lastly, when our algorithm is run on intervals in the domain $[0,\mathrm{\Delta })$, then we only know that $\alpha \in \{1,\mathrm{\dots },\mathrm{\Delta }-1\}$. Hence, to bound the approximation factor of our algorithm on such instances, we consider all possible values of $\alpha \in \{1,\mathrm{\dots },\mathrm{\Delta }-1\}$ and pick the minimum approximation factor for these cases, which establishes the lemma. $◀$

By construction, $𝒜$ consists of the following:

• $\mathrm{■}$

  $4k-4$ recursive instances of the algorithm, each on input domains of length at most $k-1$,

• $\mathrm{■}$

  at most $2k-2$ many stored intervals (in each $L_i$ and $R_i$).

Then, letting $S(k)$ denote the space used by an instance of Algorithm 1 on a domain of length $k$, we obtain the recurrence

which implies $S(k)=O(4^k{k}^k)$. $◀$

Let $𝒜$ be any deterministic algorithm for random-order unit-length interval selection on the restricted domain $[0,\mathrm{\Delta })$ that computes an $\alpha$-approximation in expectation (over the random order of the stream) using space $O(s)$. We use $𝒜$ as a black-box to present an algorithm for unrestricted domains.

To this end, for all $i\in \mathbb{Z}$, we first define the window $W_i^{\mathrm{\Delta }}=[i,i+\mathrm{\Delta })$. Initially, we mark every window $\{W_i^{\mathrm{\Delta }}:i\in \mathbb{Z}\}$ as inactive. For each interval $I$ arriving in the stream, let ${𝒲}_I=\{W_i^{\mathrm{\Delta }}:I\subseteq W_i^{\mathrm{\Delta }}\}$ be the set of windows that fully contain $I$. For each $W\in {𝒲}_I$, if $W$ is marked inactive, create a new instance of $𝒜$ corresponding to $W$, and feed $I$ into $𝒜$. Then mark $W$ as active. Otherwise, if $W$ is already marked active then there is already an instance of $𝒜$ running that corresponds to $W$. In this case, we feed the interval $I$ into the instance of $𝒜$. We note that, as a technicality, whenever an interval $I=[a,b]$ is to be fed into an instance $𝒜$ corresponding to a window $W_i^{\mathrm{\Delta }}$ then $𝒜$ is given the transformed interval $I^{\prime }=[a-i,b-i]$ so that $𝒜$’s input is contained within the restricted domain $[0,\mathrm{\Delta })$.

For each window $W$, let $OUT(W)$ denote the output from the instance of $𝒜$ corresponding to $W$ at the end of the stream. We implicitly transform each interval in $OUT(W)$ back so that they correspond to intervals on the unrestricted domain. At the end of the stream output a maximum independent set of intervals from

We optimize the space used by the algorithm by only storing the set of windows that are marked as active, i.e. each window is implicitly marked as inactive until the time it is explicitly marked as active. Then, a window marked as inactive uses zero space.

The space used by the algorithm is precisely the space used by windows marked as active, and each window uses space $O(s+1)=O(s)$ (to store $𝒜$ as well as mark it active). For each window $W_i^{\mathrm{\Delta }}$, define $W_i^{\mathrm{\Delta }}(L)=[i-1,i-1+\mathrm{\Delta })$ and $W_i^{\mathrm{\Delta }}(R)=[i+1,i+1\mathrm{\Delta })$ to be the windows shifted by one to the left and the right, respectively. Then define

Now define

Next, for every interval $I$, there exists exactly $\mathrm{\Delta }-1$ many values of $j$ such that $I\subseteq W_j^{\mathrm{\Delta }}$. Therefore $|{𝒲}^{\prime }|\le 3\cdot \mathrm{\Delta }\cdot |OPT|$. Also, the set of windows marked as active must be a subset of ${𝒲}^{\prime }$. If not, there is a window marked as active that intersects no interval in $OPT$, and so there is an interval in $𝒮$ that intersects no interval in $OPT$. This contradicts the maximality of a maximum independent set. It follows that the total space used by the algorithm is bounded by

For any window $W$, the set of intervals in $𝒮$ contained in $W$ is independent of the order of $𝒮$. Therefore, the substream of $𝒮$ on $W$ is also a random-order stream²²2This is where our argument adds on to the similar argument by [11]..

Next, for each $j\in [\mathrm{\Delta }]$, define the set of disjoint windows ${𝕎}_j=\{W_{j+a\mathrm{\Delta }}^{\mathrm{\Delta }}:a\in \mathbb{Z}\}$ and define $OP{T}_j=\{I\in OPT:\exists W\in {𝕎}_j\text{ s.t. }I\subseteq W\}$. Then, using that every interval in $OPT$ is contained in exactly $\mathrm{\Delta }-1$ windows and only a single window from any given ${𝕎}_j$,

Therefore, there exists some $k\in [\mathrm{\Delta }]$ such that

We now consider the set of windows ${𝕎}_k$. Each window in ${𝕎}_k$ is disjoint so ${\bigcup }_{W\in {𝕎}_k}OUT(W)$ is a valid independent set of the intervals of $𝒮$. Then, taking the expectation over the random order of the stream,

This meta-algorithm for unrestricted domains is deterministic. Therefore, the final algorithm for unrestricted domains is deterministic if and only if $𝒜$ is deterministic. $◀$

The proof is by combining Algorithm 1 with Lemma 14 to obtain an algorithm for random-order unit-length interval streams without any restrictions on the input domain. We first consider the space used by this approach. We then lower bound the expected approximation factor achieved on unrestricted domains with a function that only depends on the integer window length $\mathrm{\Delta }$ (from Lemma 14), and finally numerically optimise this function.

From Subsection 3.2, on a window of length $\mathrm{\Delta }$, we run an algorithm with domain size $\mathrm{\Delta }+2$. Then, from Lemmas 13 and 14, this yields an algorithm for unrestricted domains that uses

words of space, where $S(k)$ denotes the space used by an instance of the algorithm instantiated on a domain of length $k$ (from Lemma 13). Then, when $\mathrm{\Delta }=O(1)$, this space collapses to become $O(|OPT|)$.

We now consider the approximation factor of the unrestricted algorithm. Observe that a largest independent set in the window $[0,\mathrm{\Delta })$ is of size at most $\mathrm{\Delta }-1$. Therefore, combining Lemmas 12 and 14, for any $\mathrm{\Delta }$, there is an algorithm for random-order unit-length interval selection on unrestricted domains that achieves an expected approximation factor of

It remains to pick a suitable constant $\mathrm{\Delta }$. Computing (Equation 3) numerically with $\mathrm{\Delta }=5,000$ (using the recurrence relation for $out(\cdot )$ of Lemma 12) yields a lower bound of (slightly) more than $0.7401$ for the expected approximation factor, completing the proof. We discuss the choice of $\mathrm{\Delta }$ further in the full version of this paper. $◀$