Streaming Algorithms for Partitioning Integer Sequences

Christian Konrad, László Kozma

We study the problem of partitioning integer sequences in the one-pass data streaming model. Given is an input stream of integers $X\in \{0,1,\dots ,m{\}}^n$ of length $n$ with m…