Dynamic algorithms for LIS and distance to monotonicity

In this paper, we provide new approximation algorithms for dynamic variations of the longest increasing subsequence (LIS) problem, and the complementary distance to monotonicity (DTM) 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 DTM with polylogarithmic worst-case update time and a constant factor approximation algorithm for LIS with worst-case update time Õ(n є) for any constant є > 0.