Two very efficient approximation algorithms for the longest increasing subsequence

Michael Saks

Rutgers

Abstract

The longest increasing subsequence (LIS) of a finite sequence has been the subject of much study within combinatorics and probability. As a computational problem it is a classic example of a problem efficiently solved by dynamic programming. Simple algorithms are known that run in time O(n log(n)) where n is the length of the array.

In recent years, many algorithmic problems have been revisited under the assumption that the input is so large that one can only afford restricted access to it, and one is willing to settle for an approximation to the solution. In this talk, I'll discuss joint work with C. Seshadhri, in which we study the LIS problem from this perspective in two distinct models of computation.

In the standard computational model we obtain an approximation algorithm that runs in time polylogarithmic in the input size. For any chosen constant c > 0, the