Fully dynamic approximation of LIS in polylogarithmic time

DOI10.1145/3406325.3451137MaRDI QIDQ6087034zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.09761

zbMATH Keywords

dynamic data structurelongest increasing subsequencesparsification

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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 $mathcalO((1/epsilon{)}^{mathcalO(1/epsilon)})$-approximation of LIS under both operations with worst-case update time $mathcalildeO(n^{epsilon})$, for any constant $epsilon>0$. We exponentially improve on their result by designing an algorithm that maintains an $(1+epsilon)$-approximation of LIS under both operations with worst-case update time $mathcalildeO(epsilo{n}^{-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 so-called ErdH{o}s-Szekeres partitioning, in which we seek a partition of a given permutation of $1,2,ldots,n$ into $mathcalO(sqrtn)$ monotone subsequences. This problem has been repeatedly stated as one of the natural examples in which we see a large gap between the decision-tree complexity and algorithmic complexity. The result of Mitzenmacher and Seddighin implies an $mathcalO(n^{1+epsilon})$ time solution for this problem, for any $epsilon>0$. Our algorithm (in fact, its simpler decremental version) further improves this to $mathcalildeO(n)$.

Cited in

(2)

• A much better polynomial time approximation of consistency in the LR calculus
• Streaming and query once space complexity of longest increasing subsequence

This page was built for publication: Fully dynamic approximation of LIS in polylogarithmic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087034)