2015/01/09 by Cabello, Sergio, Pérez-Lantero, Pablo
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1501.02285
A set of intervals is independent when the intervals are pairwise disjoint. In the interval selection problem we are given a set \mathbbI of intervals and we want to find an independent subset of intervals of largest cardinality. Let α(\mathbbI) denote the cardinality of an optimal solution. We discuss the estimation of α(\mathbbI) in the streaming model, where we only have one-time, sequential access to the input intervals, the endpoints of the intervals lie in \1,...,n \, and the amount of the memory is constrained. For intervals of different sizes, we provide an algorithm in the data stream model that computes an estimate α of α(\mathbbI) that, with probability at least 2/3, satisfies \tfrac 12(1-ε) α(\mathbbI) ≤ α≤ α(\mathbbI). For same-length intervals, we provide another algorithm in the data stream model that computes an estimate α of α(\mathbbI) that, with probability at least 2/3, satisfies \tfrac 23(1-ε) α(\mathbbI) ≤ α≤ α(\mathbbI). The space used by our algorithms is bounded by a polynomial in ε-1 and log n. We also show that no better estimations can be achieved using o(n) bits of storage. We also develop new, approximate solutions to the interval selection problem, where we want to report a feasible solution, that use O(α(\mathbbI)) space. Our algorithms for the interval selection problem match the optimal results by Emek, Halldórsson and Rosén [Space-Constrained Interval Selection, ICALP 2012], but are much simpler.