Interval Selection in Sliding Windows

Abstract

We initiate the study of the Interval Selection problem in the (streaming) sliding window model of computation. In this problem, an algorithm receives a potentially infinite stream of intervals on the line, and the objective is to maintain at every moment an approximation to a largest possible subset of disjoint intervals among the $L$ most recent intervals, for some integer $L$. We give the following results: - In the unit-length intervals case, we give a $2$-approximation sliding window algorithm with space $\tilde{\mathrm{O}}(|OPT|)$, and we show that any sliding window algorithm that computes a $(2-\epsilon )$-approximation requires space $\hat{I}\text{c◯}(L)$, for any $\epsilon >0$. - In the arbitrary-length case, we give a $(\frac{11}{3}+\epsilon )$-approximation sliding window algorithm with space $\tilde{\mathrm{O}}(|OPT|)$, for any constant $\epsilon >0$, which constitutes our main result. We also show that space $\hat{I}\text{c◯}(L)$ is needed for algorithms that compute a $(2.5-\epsilon )$-approximation, for any $\epsilon >0$. Our main technical contribution is an improvement over the smooth histogram technique, which consists of running independent copies of a traditional streaming algorithm with different start times. By employing the one-pass $2$-approximation streaming algorithm by Cabello and Pérez-Lantero [Theor. Comput. Sci. '17] for Interval Selection on arbitrary-length intervals as the underlying algorithm, the smooth histogram technique immediately yields a $(4+\epsilon )$-approximation in this setting. Our improvement is obtained by forwarding the structure of the intervals identified in a run to the subsequent run, which constrains the shape of an optimal solution and allows us to target optimal intervals differently.

22 pages, 6 figures