Fast Algorithms for Bounded-Range LIS Approximation

We introduce an improvement to additive approximation of Longest Increasing Subsequence (LIS) of a sequence with a bounded number of unique elements. In particular, for a sequence of length with unique elements and additive error paramenter, we present an algorithm that approximate the size of ’s LIS within ± using (⁻²) · (log ⁻¹) samples and (⁻²) · (log , log ⁻¹) runtime. Our approache introduces small adjustments to the previously known algorithm for this problem, due to [5], resulting in a polynomial runtime algorithm which uses less queries by a factor of ⁻¹. Similar approaches can also be applied to estimating edit distance to monotonicity in 2-dimenstional array and ₁ edit distance of a sequence within sublinear time using (, ⁻¹) queries.M.Eng