On distance to monotonicity and longest increasing subsequence of a data stream
Funda Ergün, Hossein Jowhari · Symposium on Discrete Algorithms · 2008
In this paper we consider problems related to the sortedness of a data stream. First we investigate the problem of estimating the distance to monotonicity; given a sequence of length n, we give a deterministic (2 + e)-approximation algorithm for estimating its distance to monotonicity in space O(1/e2 log2 (en)). This improves over the randomized (4 + e)-approximation, algorithm of [3]. We then consider the problem of approximating the length of the longest increasing subsequence of an input stream of length n. We use techniques from multi-party communication complexity combined with a fooling set approach to prove that any O(1)-pass deterministic streaming algorithm that approximates the length of the longest increasing subsequence within 1 + e requires Ω(√n) space. This proves the conjecture in [3] and matches the current upper bound.