
Dynamic Longest Increasing Subsequence and the ErdösSzekeres Partitioning Problem
In this paper, we provide new approximation algorithms for dynamic varia...
read it

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
We present the first algorithm for maintaining a maximal independent set...
read it

Dynamic Matching: Reducing Integral Algorithms to ApproximatelyMaximal Fractional Algorithms
We present a simple randomized reduction from fullydynamic integral mat...
read it

Improved Dynamic Algorithms for Longest Increasing Subsequence
We study dynamic algorithms for the longest increasing subsequence (LIS)...
read it

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
We introduce a notion for hierarchical graph clustering which we call th...
read it

NearOptimal Fully Dynamic Densest Subgraph
We give the first fully dynamic algorithm which maintains a (1+ϵ)approx...
read it

An inplace, subquadratic algorithm for permutation inversion
We assume the permutation π is given by an nelement array in which the ...
read it
Fully Dynamic Approximation of LIS in Polylogarithmic Time
We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under (i) inserting an element, and (ii) deleting an element of an array. In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designed an algorithm that maintains an 𝒪((1/ϵ)^𝒪(1/ϵ))approximation of LIS under both operations with worstcase update time Õ(n^ϵ), for any constant ϵ>0. We exponentially improve on their result by designing an algorithm that maintains an (1+ϵ)approximation of LIS under both operations with worstcase update time Õ(ϵ^5). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification. A particularly interesting consequence of our result is an improved solution for the socalled ErdősSzekeres partitioning, in which we seek a partition of a given permutation of {1,2,…,n} into 𝒪(√(n)) monotone subsequences. This problem has been repeatedly stated as one of the natural examples in which we see a large gap between the decisiontree complexity and algorithmic complexity. The result of Mitzenmacher and Seddighin implies an 𝒪(n^1+ϵ) time solution for this problem, for any ϵ>0. Our algorithm (in fact, its simpler decremental version) further improves this to Õ(n).
READ FULL TEXT
Comments
There are no comments yet.