Streaming Approximation Algorithms Using Amnesic Dynamic Programming

Abstract

We consider the problem of finding the distance to monotonicity of a data stream. Exact algorithms take linear space, but allowing the introduction of an error factor of $(1+\varepsilon)$ leads to efficient algorithms that take polylogarithmic space. This is particularly important in situations where the entire data stream cannot fit simultaneously in memory, as we can trade a small amount of error for a massive performance improvement. In this thesis, we consider both randomized and deterministic approaches to such approximation algorithms. We give an exposition of the randomized and deterministic algorithms provided by Saks and Seshadri, and Naumovitz and Saks, respectively. The primary contribution of this thesis is the demonstration of a technique for establishing a lower bound on the space complexity of a divide-and-conquer deterministic approach. This strategy shows the existing lower bound without needing to use a reduction. Moreover, we suggest a means by which this could be extended to achieve an even stronger bound. The contribution of this thesis for the randomized algorithm is the construction of a lower bound on the function that determines the rate at which subproblems decay. We then use this in an empirical analysis of the optimal space bound that suggests that the current randomized algorithm is asymptotically optimal.