Interval Selection in Sliding Windows
<|reference_start|>Interval Selection in Sliding Windows: 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-\varepsilon)$-approximation requires space $\Omega(L)$, for any $\varepsilon > 0$.   - In the arbitrary-length case, we give a $(\frac{11}{3}+\varepsilon)$-approximation sliding window algorithm with space $\tilde{\mathrm{O}}(|OPT|)$, for any constant $\varepsilon > 0$, which constitutes our main result.   We also show that space $\Omega(L)$ is needed for algorithms that compute a $(2.5-\varepsilon)$-approximation, for any $\varepsilon > 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\'{e}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+\varepsilon)$-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.<|reference_end|>
@article{alexandru2024interval,
    title={Interval Selection in Sliding Windows},
    author={Cezar-Mihail Alexandru, Christian Konrad},
    journal={arXiv preprint arXiv:2405.09338},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.09338},
    primaryClass={cs.DS}
}