What does this research mean for the field?

A one-pass streaming algorithm can achieve an expected approximation factor of 0.7401 for the Unit Interval Selection problem in uniformly random ordered streams, using space linear in the size of an optimal solution. Novelty: ClaimNovelty.NOVEL_FINDING. Consensus alignment: ConsensusAlignment.CHALLENGES_CONSENSUS.

What question did this study set out to answer?

The study aims to improve the approximation factor for selecting disjoint intervals from random order streams using efficient algorithms.

February 27, 20260 citationsOpen Access

Unit Interval Selection in Random Order Streams

CACezar-Mihail AlexandruUniversity of Bristol ADAdithya DiddapurUniversity of Bristol YMYannic MausGraz University of Technology

Key Points

The study aims to improve the approximation factor for selecting disjoint intervals from random order streams using efficient algorithms.
Developed a one-pass streaming algorithm for random order streams.
Achieved an expected approximation factor of 0.7401 using space O(|OPT|).
Analyzed algorithm performance for restricted domain [0, Δ) and established recursive instances.
Demonstrated improved performance compared to previous adversarial models with a best approximation of (2/3).
Proved that algorithms aiming for an approximation above 8/9 require Ω(n) space.
Established a lower bound utilizing communication complexity arguments.

Abstract

We consider the Unit Interval Selection problem in the one-pass random order streaming model. In this setting, an algorithm is presented with a sequence of n unit-length intervals on the line that arrive in uniform random order, one at a time, and the objective is to output (an approximation of) a largest set of disjoint intervals using space linear in the size of an optimal solution. Previous work only considered adversarially ordered streams and established that, within these space constraints, a (2/3)-approximation can be achieved in such streams, and this is best possible, in that going beyond such an approximation factor requires space Ω(n) Emek et al., TALG'16. In this work, we show that an improved expected approximation factor can be achieved if the input stream is in uniform random order, where the expectation is taken over the stream order. More specifically, we give a one-pass streaming algorithm with expected approximation factor 0.7401 that uses space O(|OPT|), where OPT denotes an optimal solution. We also show that random order algorithms with expected approximation factor above 8/9 require space Ω(n), and algorithms that compute a better than 2/3-approximation with probability above 2/3 also require Ω(n) space. On a technical level, we design an algorithm for the restricted domain 0, Δ), for some constant Δ, and use standard techniques to obtain an algorithm for unrestricted domains. For the restricted domain [0, Δ), we run O(Δ) recursive instances of our algorithm, with each instance targeting the situation where a specific interval of an optimal solution arrives first. We establish the interesting property of our algorithm that it performs worst when the input stream consists solely of a set of independent intervals. It then remains to analyse the algorithm on these simple instances. Our lower bound is proved via communication complexity arguments, similar in spirit to the robust communication lower bounds established by [Chakrabarti et al., Theory Comput. 2016.

Perguntar à IA

Bookmark

View Full Paper