2014/04/07 by Christian Konrad, Konrad, Christian, László Kozma +1
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1404.1732
openalex publication_date 2014/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of partitioning integer sequences in the one-pass data streaming model. Given is an input stream of integers X ∈ \0, 1, …, m \n of length n with maximum element m, and a parameter p. The goal is to output the positions of separators splitting the input stream into p contiguous blocks such that the maximal weight of a block is minimized. We show that computing an optimal solution requires linear space, and we design space efficient (1+ε)-approximation algorithms for this problem following the parametric search framework. We demonstrate that parametric search can be successfully applied in the streaming model, and we present more space efficient refinements of the basic method. All discussed algorithms require space O( \frac1ε polylog (m,n,\frac1ε)), and we prove that the linear dependency on \frac1ε is necessary for any possibly randomized one-pass streaming algorithm that computes a (1+ε)-approximation.