Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance

Michael Saks, C. Seshadhri

Approximating the length of the longest increasing sequence (LIS) of an array is a well-studied problem. We study this problem in the data stream model, where the algorithm is allo…