TY - GEN

T1 - A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity

AU - Naumovitz, Timothy

AU - Saks, Michael

PY - 2015

Y1 - 2015

N2 - 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 ω (√n) [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 ω (1/εlog2 (n)) and any randomized algorithm requires space ω (1/ε log2 (n)/ log log (n)).

AB - 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 ω (√n) [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 ω (1/εlog2 (n)) and any randomized algorithm requires space ω (1/ε log2 (n)/ log log (n)).

UR - http://www.scopus.com/inward/record.url?scp=84938254973&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938254973&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973730.83

DO - 10.1137/1.9781611973730.83

M3 - Conference contribution

AN - SCOPUS:84938254973

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1252

EP - 1262

BT - Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

PB - Association for Computing Machinery

T2 - 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Y2 - 4 January 2015 through 6 January 2015

ER -