A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
Timothy Naumovitz, Michael J. Saks · 2014
The distance to monotonicity of a sequence of n numbers is the minimum number of entries whose deletion leaves an increasing sequence. We give the first deterministic streaming algorithm that approximates the distance to monotonicity within a 1 + ε factor for any fixed ε > 0 and runs in space polylogarithmic in the length of the sequence and the range of the numbers. The best previous deterministic algorithm achieving the same approximation factor required space [9]. Previous polylogarithmic space algorithms were either randomized [10], or had approximation factor no better than 2 [8]. We also present space lower bounds for this problem: Any deterministic streaming algorithm that gets a 1 + ε approximation requires space and any randomized algorithm requires space .