Unit Interval Selection in Random Order Streams
Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, Kheeran K. Naidu · 2026
Read Unit Interval Selection in Random Order Streams by Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, Kheeran K. Naidu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-08937.txt.
Introduction
Cezar-Mihail Alexandru and colleagues improve unit interval selection in random-order streams. An algorithm sees unit-length intervals arrive in random order and must output a largest disjoint set using space proportional to the optimum. Their one-pass method reaches an expected approximation factor of 0.7401 with space proportional to the optimum, and factors above 8/9 demand at least input-size space.
Catalog record
| CREATOR | Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, Kheeran K. Naidu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64009 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.08937
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unit Interval Selection in Random Order Streams Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, Kheeran K. Naidu 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 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 ) (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 ) \Omega(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 0.7401 that uses space O ( | O P T | ) O(|OPT|) , where O P T OPT denotes an optimal solution. We also show that random order algorithms with expected approximation factor above 8 / 9 8/9 require space Ω ( n ) \Omega(n) , and algorithms that compute a better than 2 / 3 2/3 -approximation with probability above 2 / 3 2/3 also require Ω ( n ) \Omega(n) space. On a technical level, we design an algorithm for the restricted domain [ 0 , Δ ) [0,\Delta) , for some constant Δ \Delta , and use standard techniques to obtain an algorithm for unrestricted domains. For the restricted domain [ 0 , Δ ) [0,\Delta) , we run O ( Δ ) O(\Delta) 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]. 1 Introduction In the one-pass streaming model of computation, an algorithm is presented with a stream of input items that, a priori, arrive in arbitrary order. The algorithm is tasked with computing a solution while maintaining a memory of size sublinear in the length of the input stream. We consider the Unit Interval Selection problem in the streaming model. In this problem, the input stream consists of n closed unit-length intervals \mathcal{S} on the line, presented to the algorithm in arbitrary order, and the objective is to compute a pairwise non-overlapping subset \mathcal{I}\subseteq\mathcal{S} of largest cardinality. Emek et al. [ 12 ] initiated the study of Unit Interval Selection in the one-pass streaming model. They gave a 2/3 -approximation algorithm that uses O(|OPT|) words 1 1 1 A word is the amount of space required to store a single interval. of space, where OPT denotes an optimal solution, and showed that \Omega(n) bits of space are necessary for algorithms with even slightly better approximation guarantees, which renders their algorithm space optimal. Subsequently, Cabello and Pérez-Lantero [ 7 ] gave a simpler algorithm with the same guarantee. We emphasize that these results hold for streams that are in adversarial/arbitrary order. Given that the adversarial order setting is fully understood, in this paper, we ask whether improved algorithms are possible if the input stream is in uniform random order. Indeed, random order streams have received significant attention, and, for many problems, improvements beyond known lower bounds that hold for adversarial orderings are known, such as Quantile Estimation [ 13 ] , Maximum Matching [ 15 , 5 , 2 ] , Bounded Degree Property Testing [ 17 ] , and edge-arrival Set Cover [ 16 ] . Lower bounds for random order streams were pioneered by Chakrabarti et al. [ 9 ] , with subsequent work [ 8 ] further developing these ideas. The ideas from [ 8 ] have since been employed in various random order streaming lower bound proofs, including [ 2 ] and [ 3 ] . The random order setting, which assumes worst-case instances and random order arrivals, is a less pessimistic setting than the arbitrary order setting, which assumes both worst-case instances and worst-case orderings, and is therefore more relevant from a practitioner’s point of view. 1.1 Our Results As our main result, we show that we can go beyond the 2/3 -approximation barrier for adversarial order streams when considering a uniform random arrival order. Theorem 1 . There is a deterministic one-pass O(|OPT|) words of space streaming algorithm for Unit Interval Selection on random order streams with expected approximation factor 0.7401 , where the expectation is taken over the random order of the stream. We then complement our algorithm with the following limitation result: Theorem 2 . Let \epsilon>0 be any small constant. Then: 1. Any randomized one-pass streaming algorithm for random-order Unit Interval Selection with expected approximation factor 8/9+\epsilon must use \Omega(n) bits of space. 2. For any \delta>0 , any randomized one-pass streaming algorithm for random-order Unit Interval Selection with approximation factor 2/3+\delta that succeeds with probability at least 2/3+\epsilon on any input instance must use \Omega(n) bits of space. The expectation in (1) and the probability in (2) are taken over both the stream order and the random choices of the algorithm. We note that, in the previous theorem, (1) immediately follows from (2), however, the result stated in (1) is more suitable for comparison to our algorithmic result. Furthermore, the result in (2) explains why our algorithm can only go beyond the 2/3 -approximation barrier that holds for adversarial order streams in expectation , and not with high constant probability. Our algorithmic result combined with our lower bound result show that the optimal achievable approximation ratio lies in the interval [0.7401,0.\overline{8}] , and we leave it as a great open question to further narrow this gap. 1.2 Techniques We will now discuss the main ideas behind both our algorithm and our lower bound. The Algorithm. 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,\Delta) , for some constant integer \Delta , and has approximation factor \alpha , produces an algorithm for unrestricted domains with only a constant factor blow-up in space and a factor (\Delta-1)/\Delta blow-up in the approximation factor [ 11 ] . We thus see that it is enough to design an algorithm for the restricted domain [0,\Delta) , for some large but constant \Delta , large enough so as to minimize the impact of the factor (\Delta-1)/\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