Title: Approximating the longest increasing subsequence in polylogarithmic time
Speaker: Michael Saks, Rutgers University
Date: Wednesday, September 8, 2010 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Let n denote the size of the array. Simple O(n log n) algorithms are known for solving this problem exactly.
While this algorithm runs in nearly linear time, with the increasing ubiquity of enormous data sets, there has been considerable interest in developing algorithms for problems like LIS that operate by sampling the input in a small number of places and obtain good approximations to the answer.
In this talk I'll discuss recent work of C. Seshadhri and myself, in which we develop a polylogarithmic time randomized algorithm that for any constant C > 0, outputs an approximation to the length of the LIS that (with high probability) is accurate to within an additive Cn. Previously, the best known polylogarithmic time algorithms could achieve only an additive n/2 approximation.
It is not hard to see that uniform random sampling of the input is not sufficient to get a good approximation to the LIS. Our algorithm uses random sampling that is both non-uniform and adaptive (that is the choice of points to sample depends on the values observed previously.)