Estimating the longest increasing sequence in polylogarithmic time

Abstract

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let n denote the size of the array. Simple O(n log n) time algorithms are known that determine the LIS exactly. In this paper, we develop a randomized approximation algorithm, that for any constant δ > 0, runs in time polylogarithmic in n and estimates the length of the LIS of an array up to an additive error of δn. The algorithm presented in this extended abstract runs in time (log n)O(1/δ). In the full paper, we will give an improved version of the algorithm with running time (log n) c(1/δ)O(1/δ) where the exponent c is independent of δ. Previously, the best known polylogarithmic time algorithms could only achieve an additive n/2-approximation. Our techniques also yield a fast algorithm for estimating the distance to monotonicity to within a small multiplicative factor. The distance of f to monotonicity, εf , is equal to 1 - |LIS|/n (the fractional length of the complement of the LIS). For any δ > 0, we give an algorithm with running time O((ε f-1 log n)O(1/δ)) that outputs a (1+δ)-multiplicative approximation to εf . This can be improved so that the exponent is a fixed constant. The previously known polylogarithmic algorithms gave only a 2-approximation. © 2010 IEEE.