Saeed Seddighin, Toyota Technological Institute at Chicago (TTIC)

Abstract

In this talk, I'll discuss our new approximation algorithms for the dynamic variant of the longest increasing subsequence (LIS) problem. In this setting, operations of the following form arrive sequentially:

     (i) add an element, 

     (ii) remove an element, 

     or (iii) substitute an element for another.  

At every point in time, the algorithm has an approximation to the size of the longest increasing subsequence.  We present several algorithms including a constant-factor approximation algorithm with worst-case update time ~O(n^eps) and an exact algorithm with worst-case update time ~O(n^{2/3}).

Our dynamic algorithm for LIS leads to an almost optimal algorithm for the Erdos-Szekeres partitioning problem. Erdos-Szekeres partitioning problem was introduced by Erdos and Szekeres in 1935 and was known to be solvable in time O(n^{1.5} log n). Subsequent work improves the runtime to O(n^{1.5}) only in 1998. Our dynamic LIS algorithm leads to a solution for the Erdos-Szekeres partitioning problem with runtime ~O(n^{1+eps}) for any constant eps > 0.

Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home