2021/01/18 by Mitzenmacher, Michael, Seddighin, Saeed
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2101.07360
In this paper, we provide new approximation algorithms for dynamic variations of the longest increasing subsequence (\textsfLIS) problem, and the complementary distance to monotonicity (\textsfDTM) 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 longest increasing subsequence (or distance to monotonicity). We present a (1+ε)-approximation algorithm for \textsfDTM with polylogarithmic worst-case update time and a constant factor approximation algorithm for \textsfLIS with worst-case update time O(nε) for any constant ε> 0.% n in the runtime denotes the size of the array at the time the operation arrives. Our dynamic algorithm for \textsfLIS leads to an almost optimal algorithm for the Erdös-Szekeres partitioning problem. Erdös-Szekeres partitioning problem was introduced by Erdös and Szekeres in 1935 and was known to be solvable in time O(n1.5log n). Subsequent work improve the runtime to O(n1.5) only in 1998. Our dynamic \textsfLIS algorithm leads to a solution for Erdös-Szekeres partitioning problem with runtime Oε(n1+ε) for any constant ε> 0.