# Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning
Problem111The results of this manuscript appeared in preliminary versions [24]
(STOC’20) and [25].

Michael Mitzenmacher Toyota Technological Institute at Chicago Saeed
Seddighin11footnotemark: 1

###### Abstract

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+\epsilon)$-approximation algorithm
for DTM with polylogarithmic worst-case update time and a constant factor
approximation algorithm for LIS with worst-case update time
$\tilde{O}(n^{\epsilon})$ for any constant $\epsilon>0$.

Our dynamic algorithm for LIS 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(n^{1.5}\log n)$. Subsequent work improve the runtime to $O(n^{1.5})$ only
in 1998. Our dynamic LIS algorithm leads to a solution for Erdös-Szekeres
partitioning problem with runtime $\tilde{O}_{\epsilon}(n^{1+\epsilon})$ for
any constant $\epsilon>0$.

##  1 Introduction

Longest increasing subsequence (LIS) is one of the oldest problems in computer
science. Given an array $a=\langle a_{1},a_{2},\ldots,a_{n}\rangle$ of size
$n$, LIS is defined as the largest subset of the elements whose values are
strictly increasing in the order of their indices. Distance to monotonicity
(DTM) is the dual problem. For DTM, we wish to remove the smallest number of
elements such that the remaining subsequence is increasing. LIS and DTM are
special cases of the celebrated edit distance and longest common subsequence
problems when the input strings are permutations.

The classic patience sorting solution for LIS utilizes dynamic programming and
binary search to solve LIS exactly in time $O(n\log n)$. (In what follows,
when we refer to a solution, we typically refer to the size of the LIS, but
also the corresponding increasing subsequence can be found in time
proportional to its size.) Matching lower bounds ($\Omega(n\log n)$) are known
for comparison-based algorithms [13] and solutions based on algebraic decision
trees [31]. For approximation algorithms, for any $\epsilon>0$, a
multiplicative $O(n^{\epsilon})$ approximate solution can be determined in
truly sublinear time via random sampling222For an $O(n^{\epsilon})$
approximation algorithm, one can sample $O(n^{1-\epsilon})$ many elements from
the array and report the LIS of those samples.. Surprisingly, not much is
known that improves upon this algorithm generally, although when
$n/\mathsf{LIS}(a)$ is subpolynomial we can obtain better approximation
guarantees for LIS [32, 33].

From a complexity point of view, unconditional lower bounds apply to LIS. For
instance, any algorithm that obtains an $f(n)$ approximate solution for LIS
has to make at least $n/(f(n)+1)$ value queries333A value query provides an
$i$ as input and asks for the value of $a_{i}$. to the elements of $a$ to
distinguish the case that $a$ is decreasing from the case that $a$ has an
increasing subsequence of length at least $f(n)+1$. Thus a subpolynomial
approximation algorithm for LIS in truly sublinear time is not possible in
general. Even if we are guaranteed that the solution size is
$\Theta(n^{1-\epsilon})$ (a setting for which the known complexity lower
bounds do not apply), we are not aware of any subpolynomial approximate
solution for LIS. Very recently, Rubinstein et al. [32] obtain
$O(n^{3\epsilon})$ approximation in time $\tilde{O}(n^{0.5+7\epsilon})$ in
this case. Also, these lower bounds do not hold for stronger computational
models such as quantum computation, but we do not have better general quantum
approximation algorithms.

In this work, we focus on approximation algorithms in the dynamic setting,
where at each step, the array can be updated by inserting, deleting, or
modifying an element. The goal is to maintain an approximation of the correct
value at each step. Dynamic settings for many problems have been studied, e.g.
[19, 27, 16, 4, 3, 7, 23, 5, 28]. In general, in dynamic settings the goal is
to develop an algorithm where the solution can be updated efficiently given
incremental changes to the input. In the context of graph algorithms [27, 28,
23, 4, 3, 5], such changes are usually modeled by edge addition or edge
deletion. For string problems, changes are typically modeled with character
insertion and character deletion [16, 7], as we consider here.

We provide novel approximation algorithms for LIS and DTM in the dynamic
setting. For LIS, for any $0<\epsilon<1$, we give a dynamic algorithm with
worst-case update time $\tilde{O}(n^{\epsilon})$ and approximation factor
$O_{\epsilon}(1)$; that is, for constant $\epsilon$, the approximation factor
is a constant that depends on $\epsilon$. For DTM, we present an algorithm
with approximation factor $1+\epsilon$ for any constant $\epsilon$ and worst-
case update time $O(\log^{2}n)$, where the order notation hides factors that
can depend on $\epsilon$. We primarily treat $\epsilon$ as constant since the
exponent of the $\log$ factors suppressed by the $\tilde{O}$ notation may
depend on $1/\epsilon$. Here, $n$ denotes the size of the array at the time
the operation arrives. Thus the update time does not depend on the number of
operations arrived prior to the new operation.

Problem | Approximation factor | Update time
---|---|---
LIS | $1+\epsilon$ | $\tilde{O}(\sqrt{n})$
LIS | $O((1/\epsilon)^{O(1/\epsilon)})$ | $\tilde{O}(n^{\epsilon})$
$\mathsf{LIS}^{+}$ | $O(\log n)$ | $O(\log^{3}n)$
DTM | $1+\epsilon$ | $O(\log^{2}n)$
Table 1: The results of this paper are summarized in this table.
$\mathsf{LIS}^{+}$ is a special case of LIS where only element insertion is
allowed.

###  1.1 Erdös-Szekeres partitioning problem

Our dynamic algorithm has an interesting application to a long-standing
mathematical problem, namely the Erdös-Szekeres partitioning problem. It is
well-known that any sequence of size $n$ can be decomposed into $O(\sqrt{n})$
monotone subsequences. The proof follows from a simple fact: Any sequence of
length $n$ contains either an increasing subsequence of length $\sqrt{n}$ or a
non-increasing subsequence of length $\sqrt{n}$. Thus, one can iteratively
find the maximum increasing and the maximum non-increasing subsequences of a
sequence and take the larger one as one of the solution partitions. Next, by
removing the partition from the original sequence and repeating this procedure
with the remainder of the elements we obtain a decomposition into at most
$O(\sqrt{n})$ partitions. The computational challenge, also known as the
Erdös-Szekeres partitioning problem, is to do this in an efficient way. The
above algorithm can be implemented in time $O(n^{1.5}\log n)$ if we use
patience sorting in every iteration. Bar-Yehuda and Fogel [34] improve the
runtime down to $O(n^{1.5})$ by designing an algorithm that after a
preprocessing step, solves LIS in time $O(n+k^{2})$ where the solution size is
bounded by $k$. Since any comparison-based algorithm takes time at least
$\tilde{\Omega}(n)$, the gap for Erdös-Szekeres partitioning problem has been
$\tilde{\Omega}(\sqrt{n})$ for quite a long time and the question was raised
in a number of works as an important open problem [30, 18].

We prove that via our dynamic LIS algorithm, the Erdös-Szekeres partitioning
problem can be solved in time $\tilde{O}_{\epsilon}(n^{1+\epsilon})$ for any
constant $\epsilon>0$. We assume that our algorithm performs as stated in
Table 1.

######  Theorem 1.

For any constant $\epsilon>0$, one can in time
$\tilde{O}_{\epsilon}(n^{1+\epsilon})$ partition any sequence of length $n$ of
distinct integer numbers into $O_{\epsilon}(\sqrt{n})$ monotone (increasing or
decreasing) subsequences.

###### Proof.

The proof follows directly from our algorithm for dynamic LIS. In our dynamic
setting, we start with an empty array $a$ and at every point in time we are
allowed to (i) add an element, or (ii) remove an element, or (iii) substitute
an element for another. The algorithm is able to update the sequence and
estimate the size of the LIS in time $\tilde{O}_{\epsilon}(|a|^{\epsilon})$
where $|a|$ is the size of the array at the time the operation is performed.
Moreover, the approximation factor of our algorithm is constant as long as
$\epsilon$ is constant. More precisely, our algorithm estimates the size of
the longest increasing subsequence within a multiplicative factor of at most
$(1/\epsilon)^{O(1/\epsilon)}$. It follows from our algorithm that by spending
additional time proportional to the reported estimation, our algorithm is able
to also find an increasing subsequence with size equal to the reported length.

Given a sequence of length $n$ with distinct numbers, we use the dynamic
algorithm for LIS to decompose it into $O_{\epsilon}(\sqrt{n})$ monotone
subsequences in time $\tilde{O}_{\epsilon}(n^{1+\epsilon})$. To do so, we
initialize two instances of our dynamic algorithm that keep an approximation
to the longest increasing subsequence and the longest decreasing subsequence
of the array. More precisely, in the first instance, we insert all elements of
the array exactly the same way they appear in our sequence and in the second
instance we insert the elements in the reverse order. Thus the dynamic
algorithm for the second instance always maintains an approximation to the
longest decreasing subsequence of our array.

In every iteration, we estimate the size of the longest increasing and longest
decreasing subsequences of the array via the dynamic LIS algorithm. We then
choose the maximum one and ask the algorithm to give us the sequence
corresponding to the solution reported. Finally, we remove the elements from
both instances of the dynamic algorithm and repeat the same procedure for the
remainder of the elements.

The total runtime of our algorithm is $\tilde{O}_{\epsilon}(n^{1+\epsilon})$
since we insert $n$ elements in each of the instances and then remove $n$
elements which amounts to $2n$ operations for each instance that runs in time
$\tilde{O}_{\epsilon}(n^{1+\epsilon})$. Moreover, because at every point in
time the maximum estimate we receive from each of the dynamic algorithms is at
least a constant fraction of the actual longest increasing subsequence, we
repeat this procedure at most $O_{\epsilon}(\sqrt{n})$ times. Therefore, we
decompose the sequence into $O_{\epsilon}(\sqrt{n})$ monotone subsequences. ∎

######  Remark 1.

The constant factor hidden in the $O$ notation for the number of partitions is
optimal in neither the algorithm of Theorem 1 nor the previous algorithm of
[34] nor the simple greedy algorithm that runs patience sorting in every step.

###  1.2 Subsequent Work

Since our dynamic algorithm has constant approximation factor, in order to
make sure the number of partitions remains $O(\sqrt{n})$, one needs to set
$\epsilon$ to constant and therefore the gap between our runtime of
$\tilde{O}(n^{1+\epsilon})$ and the lower bound of $\Omega(n)$ remains
polynomial. Two independent subsequent work further tighten the gap. Kociumaka
and Seddighin [22] improve the gap to subpolynomial by presenting a dynamic
algorithm with approximation factor $1-o(1)$ and update time $O(n^{o(1)})$.
Gawrychowski and Janczewski [15] further tighten the gap to polylogarithmic by
obtaining a similar algorithm with polylogarithmic update time (with
polynomial dependence on $1/\epsilon$). The work of Kociumaka and Seddighin
[22] also gives the first exact algorithm for dynamic LIS with sublinear
update time. Their algorithm is able to update the solution in time
$\tilde{O}(n^{2/3})$ after each operation and gives a correct solution with
probability $1-n^{-5}$.

In another subsequent work, Mitzenmacher and Seddighin [26] use the grid-
packing technique given here to obtain an improved sublinear time algorithm
for approximating LIS. Their algorithm is able to obtain an approximation of
LIS in truly sublinear time within a factor of $\Omega(\lambda^{\epsilon})$
where $\epsilon>0$ is an arbitrarily small constant factor and $\lambda$ is
the ratio of the solution size and the input size.

###  1.3 Related Work

LIS has received significant attention in the areas of property testing [11,
10, 12, 1], streaming [17, 14], and massively parallel computation (MPC) [20],
as well as in the standard algorithmic setting [13, 31, 32, 33]. Several
questions remain open about approximation algorithms for LIS. Although a
linear lower bound on the runtime is trivial when the solution size is $O(1)$,
neither convincing lower bounds nor upper bounds are known for approximating
LIS within subpolynomial multiplicative factors if the solution size is larger
($\omega(1)$) in general. For a special case when $n/\textsf{LIS}(a)$ is
subpolynomial, we can approximate the solution size within a subpolynomial
factor in sublinear time [32, 33]. In particular, Saks and Seshadhri [33]
present a $(1+\epsilon)$ approximation algorithm for LIS in sublinear time if
the ratio of $n$ over the solution size is sublogarithmic. The only prior non-
trivial dynamic algorithm for LIS that we are aware of is the work of Chen et
al. [7], where the authors present an exact dynamic algorithm for LIS with
worst-case update time $O(r+\log n)$ when the solution size is bounded by $r$.
The update time for this algorithm can grow up to $\Omega(n)$ if the solution
size is $\Omega(n)$.

When the available memory is sublinear (as it is in the streaming and the MPC
models), patience sorting can be used to compute a solution for smaller
fragments of the input. Previous work show that these local solutions can be
cleverly merged to obtain $1+\epsilon$ approximate solutions in the streaming
[17] and the MPC models [20]. In contrast, our technique for approximating LIS
is not based on patience sorting. We show it also has an application to a
streaming variant of LIS, and we expect it will have additional applications
in the future.

Distance to monotonicity (a.k.a Ulam distance) is also a very well-studied
problem [29, 2, 6, 33]. While LIS has resisted a multiplicative approximation
algorithm, DTM can be approximated within a multiplicative factor $1+\epsilon$
in time $\tilde{O}(n/d+\sqrt{n})$ when the solution size is lower bounded by
$d$ [29]. Streaming [17] and MPC [6] algorithms for DTM have also appeared.

###  1.4 Preliminaries

We consider the two problems, LIS and DTM. Input to both problems is an array
$a$ with arbitrary length. For LIS, the goal is to find the length of the
largest subsequence of elements such that their values increase according to
their indices. For DTM the goal is to determine the smallest number of
elements such that the remaining subsequence is increasing. Obviously,
$\mathsf{DTM}(a)=|a|-\mathsf{LIS}(a)$. However, an approximate solution for
one problem does not imply an approximate solution for the other (much like
maximum matching and vertex cover). We assume for simplicity and without loss
of generality that all the numbers are distinct, although one can easily
modify our algorithm to handle repeated numbers.

Our results here are for the dynamic setting. Initially, the input array is
empty ($|a|=0$). At each step, an element is either inserted at an arbitrary
position of the array or removed from an arbitrary position of the array.
(Element substitution can also be implemented with the previous two
operations, so we consider only insertions and removals.) We also study a
special case of LIS where all operations add elements to the array. We call
this problem $\mathsf{LIS}^{+}$.

We more formally define the array operations. Each insertion operation is of
the form “insert $(i,x)$” where $i$ is an integer between $1$ and the length
of the current array plus one. $i$ specifies the position of element $x$.
After this operation, all the elements whose previous index was at least $i$
will be shifted to the right. Similarly, an operation “delete $(i)$” removes
the $i$’th element of the array and element $i+1$ will replace its position.
Likewise, all the elements whose previous index was at least $i$ will be
shifted to the left.

For simplicity, in our algorithms we assume that at any point random access to
the elements is provided. That is, in every step, one can access the value of
the $i$’th element of the array as a value query. This brings an $O(\log n)$
overhead to the runtime since one needs to design a data structure that allows
us element addition, element removal, and access to the $i$’th element. Any
balanced binary tree (e.g. red-black tree) suffices for that purpose [9]. We
can also recover the position of each element of the array in logarithmic time
with a balanced binary tree.

##  2 Summary of the Results and Techniques

Our main result is a dynamic algorithm for LIS with worst-case update time
$\tilde{O}(n^{\epsilon})$ and approximation factor
$O((1/\epsilon)^{O(1/\epsilon)})$. Our algorithm is based on a novel technique
which we call grid packing. In this section, we give a high-level summary of
grid packing and our overall approach; Full proofs are given in Sections 4 and
5.

###  2.1 Block-based Algorithms

In our work, to simplify our proofs, we utilize the notion of what we call a
block-based algorithm. Very roughly speaking, a block-based algorithm starts
with an array $a$ of length $n$. It can use $f(n)$ preprocessing time, after
which it is responsible for a block of $g(n)$ operations, where each operation
has worst-case update time $h(n)$. We show in Section 3 via a simple reduction
that such a block-based algorithm can be used to obtain a dynamic algorithm
with worst-case update time $\max\\{f(n)/g(n),h(n)\\}$.

A motivating example shows the notion of block-based algorithms simplifies the
analysis. Chen et al. [7] show that when LIS for an array is upper bounded by
$r$, a dynamic algorithm can maintain the exact solution for LIS with worst-
case update time $\tilde{O}(r)$. We show that this exact algorithm yields a
dynamic $(1+\epsilon)$-approximation algorithm with worst-case update time
$\tilde{O}(\sqrt{n})$.

We first provide the intuition and explain the complications. At any point in
time, if the solution value is below $2\sqrt{n}/\epsilon$, then the runtime
guarantee is met by using the algorithm of Chen et al. [7]. Otherwise, we can
compute an exact solution, and then use the same value for up to $\sqrt{n}$
steps to maintain a valid approximation. We then spend time $\tilde{O}(n)$ for
$\sqrt{n}$ operations, leading to amortized update time of
$\tilde{O}(\sqrt{n})$. Deamortizing this approach to bound the worst-case
update time seems cumbersome. The issue is that it is not clear when we should
switch between the two algorithms. For example, if we define a threshold
$\tau$ and switch between the algorithms when the solution size crosses the
threshold $\tau$, we may go back and forth across the threshold. We could
consider multiple thresholds, but at this point we appear to be complicating
the analysis beyond what should be necessary.

Working with the framework of a block-based algorithm conveniently remedies
the problem. Assuming we start with an array $a$ of length $n$, we allow a
preprocessing time of $f(n)=O(n\log n)$ for the algorithm to compute the LIS.
We set $g(n)=\sqrt{n}$. If the LIS value $r$ is above $2\sqrt{n}/\epsilon$,
for the next $\sqrt{n}$ steps, we report $r-i$ in the $i$’th step and can be
sure that our solution is within a small range from the optimal one.
Otherwise, we use the algorithm of Chen et al. [7] with worst-case update time
$O(\sqrt{n})$ for the next $\sqrt{n}$ steps. Using the reduction, this turns
to an algorithm with worst-case update time $\tilde{O}(\sqrt{n})$ for LIS with
approximation factor $1+\epsilon$.

Corollary 4, [restated informally]. For any constant $\epsilon>0$, there
exists a dynamic algorithm for LIS with worst-case update time
$\tilde{O}(\sqrt{n})$ and approximation factor $1+\epsilon$.

###  2.2 Grid Packing and Applications

As mentioned earlier, our algorithm for LIS is based on a technique that we
call grid packing. Grid packing is defined on a table of $m\times m$ cells;
the only parameter of the problem is $m$. The problem can be thought of as a
game between us and an adversary. We introduce a number of segments on the
table. Each segment covers a consecutive set of cells in either a row or in a
column. A segment $A$ precedes a segment $B$ if every cell of $A$ is strictly
higher than every cell of $B$ and also every cell of $A$ is strictly to the
right of every cell of $B$. Two segments are non-conflicting, if one of them
precedes the other one. Otherwise, we call them conflicting. The segments we
introduce can overlap and there is no restriction on the number of segments or
the length of each segment. However, we would like to minimize the maximum
number of segments that cover a cell.

Figure 1: Segments are shown on the grid. The pair (black, orange) is
conflicting since the yellow cell (covered by the black segment) is on the
same row as the blue cell (covered by the orange segment). The following pairs
are non-conflicting: (green, black), (green, orange), (green, blue), (red,
orange), (red, blue), (black, blue).

After we introduce the segments, an adversary puts a non-negative number on
each cell of the grid. We emphasize that our segments do not depend on these
numbers, as the numbers are given after we provide our segments. The score of
a subset of cells in the table is the sum of the values in the cells, and the
overall score of the table is the maximum score of a path of length $2m-1$
from the bottom-left corner to the top-right corner. (In such a path, each
move is either up or to the right.)

The score that we obtain using our segments is the maximum sum of scores of a
non-conflicting set of segments. One can easily verify that the score of the
table is a clear upper bound on the score we obtain using any subset of non-
conflicting segments. We would like to introduce the segments in such a way
that the ratio of the score of the table over our score is always bounded by
constant, no matter how the adversary puts the numbers on the table. For a
fixed $\alpha\geq 1$ and a $\beta\geq 1$, we call a solution
$(\alpha,\beta)$-approximate if at most $\alpha$ segments cover each cell and
it guarantees a $1/\beta$ fraction of the score of the table for us for any
assignment of numbers to the table cells. We show in Section 4 that grid
packing admits an $(O(m^{\kappa}\log m),O(1/\kappa))$-approximate solution for
any $0<\kappa<1$.

Before explaining the idea behind this result, we would like to make a
connection between grid packing and LIS. Let us consider an array $a$ of
length $n$. We assume for the sake of this example that all the numbers of the
array are distinct and are in range $[1,n]$. In other words, $a$ is a
permutation of numbers in $[n]$. We map the array to a set of points on the 2D
plane by putting a point at $(i,a_{i})$ for every position $i$ of the array.

$\langle
7,2,4,1,9,6,3,5,8\rangle$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$
Figure 2: An array $\langle 7,2,4,1,9,6,3,5,8\rangle$ is mapped to the 2D
plane.

Now, divide the plane into an $m\times m$ grid, and fix a longest increasing
subsequence. The number on each cell of the grid would be equal to the
contribution of the elements in that grid cell to the fixed longest increasing
subsequence. (We emphasize that the number is not the longest increasing
subsequence inside the cell, but the contribution to the fixed longest
increasing subsequence only.) It follows that the score of the grid is exactly
equal to the size of the longest increasing subsequence. Let us assume that
the score of each segment is available. To approximate the score of the grid
(which equals the size of the LIS) we find the largest score we can obtain
using non-conflicting segments by dynamic programming. The last observation
which gives us speedup for LIS is the following: instead of using the score of
each segment (which we are not aware of), we use the size of the LIS for each
segment as an approximate value for its score. LIS of each segment can be
computed in time $\tilde{O}(n/m)$ since at most $n/m$ elements appear in every
row or every column of the grid. This quantity is clearly an upper bound on
the score of each segment but can be used to construct a global solution for
the entire array (see Section 5 for more details). In our dynamic algorithm,
every time a change is made, we only need to update the approximate score
(LIS) of the corresponding segments.

$\langle
7,\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}2\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}4\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},1,9,\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}6\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},3,5,\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}8\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\rangle$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$1$$0$$0$$0$$0$$0$$1$$1$$1$
Figure 3: An array $\langle 7,2,4,1,9,6,3,5,8\rangle$ is mapped to the 2D
plane. An LIS is shown by green points. The plane is divided into a $3\times
3$ grid. The number on each cell is the equal to the contribution of that cell
to the LIS. The score of the grid is equal to the LIS of the array. The score
of the grid is made by the path colored in green.

Our solution for grid packing is based on a combinatorial construction. The
first observation is that any path of length $2m-1$ from the bottom left to
the top right of the grid can be decomposed into several disjoint parts such
that each part is either completely in a row or completely in a column, and
further column-parts or row-parts are non-conflicting using the previous
terminology.

Figure 4: Each path from bottom-left to top-right is divided into disjoint
row-intervals or column-intervals. Row intervals are shown with orange and
column intervals are shown with blue. All row intervals are non-conflicting
and all column-intervals are also non-conflicting.

Grid packing therefore reduces to the 1-dimensional variant of grid packing,
array packing, as follows. For the array packing problem, an array of length
$m$ is given as input (with no numbers on it). Our goal is to define segments
(this time all horizontal), while keeping the maximum number of segments
covering each cell small. After we fix our solution, the adversary puts non-
negative numbers on the array cells. For any fixed interval $[x,y]$ we would
like to have a segment completely in that interval whose score is at least a
fraction of the score of that interval. More precisely, a solution for array
packing is $(\alpha,\beta)$-approximate if it covers each cell at most
$\alpha$ times and the score of any interval over the maximum score of a
segment inside it is bounded by $\beta$. Similar to grid packing, we are not
aware of the numbers when giving a solution, and the adversary is aware of our
solution before deciding which numbers to put and which interval to choose for
the comparison.

An $(\alpha,\beta)$-approximate solution for array packing yields a
$(2\alpha,2\beta)$-approximate solution for grid packing as follows. We treat
each row and each column of the grid as an array and make a separate solution
for the corresponding array packing instance. After the adversary puts the
numbers on the grid, any path from bottom left to the top right can be divided
into disjoint column intervals or row intervals, one of which provides us a
$2$ approximate solution for the score of the grid. Finally, the guarantee of
array packing enables us to prove that the above solution is
$(2\alpha,2\beta)$-approximate for grid packing.

Thus, all that remains is to provide a solution for array packing. To begin,
for each cell of the array, there should be one segment covering only that
cell. Otherwise, there is no way to compete with an adversary that puts $1$ on
that cell and 0 on the other cells and uses that cell for the chosen interval.
Thus, $m$ segments of length $1$ for the $m$ cells of the array is an
inevitable part of any solution. A first idea to extend this construction is
to put segments of length $2$ on every other cell of the array, giving $m/2$
segments covering all of the array cells, and continuing further, for any
$1\leq i\leq\log m$, we use $m/2^{i}$ segments of length $2^{i}$ to cover all
cells of the array. While with this construction at most $\log m$ segments
cover each cell, the best guarantee that we can expect for such a solution in
terms of score is a $1/\Omega(\log m)$ fraction of the score of each interval.
That is, such a solution is only $(O(\log m),O(\log m))$-approximate.

To improve the approximation factor to a constant, we make $m^{\kappa}$ copies
of each set of segments. Roughly speaking, for segments of length $2^{i}$ we
make $m^{\kappa}$ copies by right shifting the segments by $2^{i}/m^{\kappa}$
cells each time (see Section 4 for more details about this construction and
edges cases such as when $2^{i}<m^{\kappa}$). This clearly adds a
multiplicative overhead of $m^{\kappa}$ for the number of segments covering
each cell. However, as we show in Section 4 it improves the second parameter
of the approximation guarantee down to $O(1/\kappa)$ from $O(\log m)$.

Theorem 6, [restated informally]. For any $0<\kappa<1$, the grid packing
problem on an $m\times m$ grid admits an
$(\tilde{O}(m^{\kappa}),O(1/\kappa))$-approximate solution.

Grid packing is a very strong tool for approximating LIS. For example,
consider an array $a$ of length $n$ for which we wish to design a block-based
dynamic algorithm for LIS. We fix a constant $0<\kappa<1$ and set
$f(n)=\tilde{O}(n^{1+\kappa})$. Let $m=n^{1/3}$ be the size of the grid we
construct for this array. The horizontal thresholds are set in a way that
separate the elements into $m$ different pieces each containing roughly $n/m$
elements. That is, the first threshold is the value of the $n/m$’th element of
the array after sorting the numbers and so on. The vertical thresholds are set
to divide the elements into $m$ different parts each containing $n/m$
elements. That is, the first part contains the first $n/m$ elements of the
array and so on. This way, each element of the array corresponds to one unique
cell of the grid.

The most important property of this division is that every row or every column
of the grid contains at most $n/m$ elements. This property is asymptotically
maintained for the next $g(n)=n^{2/3}$ operations for which the block-based
algorithm is responsible. Obviously, this guarantee also holds for the
segments. We solve the problem in the following way: first we make a solution
for grid packing of size $m\times m$. For each segment, we make a separate
instance of the dynamic LIS problem that solves the problem for the elements
covered by that segment. Initially, we use the naive algorithm that computes
LIS from scratch every time an operation arrives. However, since each segment
corresponds to at most $O(n/m)$ elements, the worst-case update time for each
segment is $\tilde{O}(n/m)$. Moreover, each cell is covered by at most
$\tilde{O}(m^{\kappa})$ segments which means each operation modifies at most
$\tilde{O}(m^{\kappa})$ segments. Thus, the total update time is
$\tilde{O}(m^{\kappa}n/m)=\tilde{O}(n^{2/3+\kappa})$. In order to approximate
the size of the LIS, every time we run a DP on the segments to find a set of
non-conflicting segments whose total size of LIS is maximized. Notice that the
LIS of each segment is available in time $O(1)$ (since after each update we
store the size of the solution for each segment), and DP takes time
$\tilde{O}(m^{2+\kappa})$ which is basically the total number of segments we
have. This is obviously a lower bound on the actual solution size since any
partial solution for a non-conflicting set of segments can be combined to
obtain a global solution for the union of the elements in all segments.
Moreover, the size of the LIS for each segment is definitely an upper bound on
the contribution of that segment to the optimal solution. Thus, the solution
of the DP is at least an $\Omega(\kappa)$ fraction of the size of the LIS for
the entire array.

One thing to keep in mind is that updating the grid requires a more careful
analysis. Since the column divisions are based on the indices of the elements,
when we add or remove some elements, some columns may grow wider or thinner.
While the grid illustration may make it seem challenging to manage such update
operations, the actual implementation is straightforward. We define $m-1$
thresholds initially set to factors of $n/m$. Every time an element is added
or removed, in addition to updating the binary tree data structure tracking
the location of each element, we can also update the thresholds separating the
grid into subgrids..

Since the preprocessing time is $\tilde{O}(n^{1+\kappa})$ and we run the
algorithm for $n/m=O(n^{2/3})$ steps and the worst-case update time for each
operation is $\tilde{O}(n^{2/3+\kappa})$, this block-based algorithm can be
turned into a dynamic algorithm for LIS with approximation factor
$O(1/\kappa)$ and worst-case update time $\tilde{O}(n^{2/3+\kappa})$. While
this is worse than the solution given in Corollary 4 both in terms of the
approximation factor and worst-case update time, this solution can be extended
to improve the update time down to $\tilde{O}(n^{\epsilon})$ for any constant
$\epsilon>0$. All it takes to improve the update time is to replace the naive
LIS algorithm of each segment by the more clever algorithm we explained above.
While this comes at the expense of a larger approximation factor, the worst-
case update time improves. We show in Section 5 that by setting
$\kappa=\Omega(\epsilon)$ and recursing on this algorithm $O(1/\epsilon)$
times we obtain a dynamic algorithm for LIS with worst case update time
$\tilde{O}(n^{\epsilon})$ and approximation factor
$O((1/\epsilon)^{O(1/\epsilon)})$.

Theorem 9, [restated informally]. For any constant $\epsilon>0$, there exists
an algorithm for dynamic LIS whose worst-case update time is
$\tilde{O}(n^{\epsilon})$ and whose approximation factor is
$O((1/\epsilon)^{O(1/\epsilon)})$.

It follows from Theorem 9 that after reporting the estimated value of the
solution, we can also determine the corresponding sequence in time
proportional to its size. More precisely, after using DP to construct a global
solution based on partial solutions of the segment, we can find out which
segments contribute to such a solution and recursively recover the
corresponding increasing subsequences of the relevant segments. To this end,
in addition to the DP table which we use for constructing a global solution,
we also store which segments contribute to such a solution. This way, the
runtime required for determine the corresponding increasing subsequence is
proportional to the size of the solution.

######  Remark 2.

After reporting a solution of size $x$ by our dynamic LIS algorithm, our
algorithm is able to report an increasing subsequence of length $x$ in time
$O_{\epsilon}(x)$.

For the special case of $\mathsf{LIS}^{+}$ where only insertion operations are
supported, we improve the approximation factor down to $O(1/\epsilon)$.
Moreover, if one favors the update time over the approximation factor, we show
that the update time can be reduced to polylogarithmic if we allow the
approximation factor to be $O(\log n)$.

####  2.2.1 Another Example: Advisory Help

To illustrate the effectiveness of the grid packing technique, we bring yet
another example, this time in the context of streaming algorithms. It has been
shown that LIS can be approximated within a factor of $1+\epsilon$ in the
streaming model with memory $O(\sqrt{n})$ [17]. Moreover, matching lower
bounds are also provided by Gál and Gopalan [14]. They show that it is
impossible to beat the $\Omega(\sqrt{n})$ barrier with any deterministic
algorithm that runs in a constant number of rounds and obtains a constant
factor approximation. We show that this can be improved with a randomized
algorithm that reads the input in a particular order. This notion is called
advisory help and has been previously studied [8] to provide graph algorithms
in the streaming model.

In such a setting, we design a streaming algorithm but we ask the adversary to
give us the input in a particular order. To avoid losing information, elements
come in the form $(i,a_{i})$ which specifies both the position and the value
of each element. We show that in three rounds we can obtain an $O(1/\kappa)$
approximation with memory $\tilde{O}(n^{2/5+\kappa})$. Roughly speaking, in
the first round we sample $m=n^{1/5}$ elements from the array and we set
horizontal lines of the grid based on their values. Vertical lines just evenly
divide the elements based on their indices into portions of size $n/m$.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$18$$19$$20$$21$$22$$23$$24$$25$$1$$6$$11$$16$$21$$2$$7$$12$$17$$22$$3$$8$$13$$18$$23$$4$$9$$14$$19$$24$$5$$10$$15$$20$$25$
Figure 5: Order of the ways that the elements of the array are given to us are
shown in this figure. Figure on the left shows the order of elements in the
second round and the figure on the right shows the order of the element in the
third round.

In the second round, we ask the adversary to give us the elements of the array
but in the row order (shown in Figure 5). In this round, we compute the
solution for horizontal segments. Each segment contains at most
$\tilde{O}(n/m)=\tilde{O}(n^{4/5})$ element with high probability and
therefore using the algorithm of [17] we can approximate its LIS within factor
$1+\epsilon$ with memory $\tilde{O}(n^{2/5})$. Since each cell is covered by
at most $\tilde{O}(m^{\kappa})$ segments, at each step we solve the problem
for at most $\tilde{O}(m^{\kappa})$ segments simultaneously which adds an
overhead of $\tilde{O}(m^{\kappa})=\tilde{O}(n^{\kappa})$ to the memory of the
algorithm. Thus the overall memory is bounded by $\tilde{O}(n^{2/5+\kappa})$.
The third round solves the problem for vertical segments similar to the
horizontal ones. The only difference is that this time we ask the adversary to
give us the elements in the column order. Once all the solutions for all
segments are available, we run a DP with memory
$\tilde{O}(m^{2+\kappa})=\tilde{O}(n^{2/5+\kappa})$ to approximate the final
solution size. Notice that this solution is not refuted by the impossibility
result of [17] since it both uses randomization and extra help from the
adversary. In order for the adversary to provide us the array elements in this
particular order, she may need to sort the numbers based on their values.
However, sorting does not overly simplify the problem. Computing the LIS of an
array is equally hard if the elements are given in the sorted order!

###  2.3 Distance to Monotonicity

Additionally, we present a dynamic algorithm for DTM. Distance to monotonicity
seems to be more tractable than LIS since previous work obtain much more
efficient algorithms for DTM than LIS [2, 17, 29]. In particular, there are
several known techniques for approximating DTM within a constant factor. As an
example, one can model the problem with a graph containing $n$ vertices each
corresponding to an element. There is an edge between two vertices, if the
corresponding elements are not increasing. While in this interpretation, LIS
is equivalent to the largest independent set of the graph, DTM translates to
vertex cover which can be approximated within a factor of $2$ by maintaining a
maximal matching. As part of our algorithm, we show that such a maximal
matching can be maintained with worst-case update time $O(\log^{2}n)$ which
yields a dynamic algorithm for DTM with approximation factor $2$ and worst-
case update time $O(\log^{2}n)$.

However, we further strengthen this result by improving the approximation
factor down to $1+\epsilon$ while keeping the update time intact. The heart of
our improvement is based on an exact algorithm for computing DTM when an
approximate solution is available. We show in Section 6 that given random
access to the elements of an array $a$ of size $n$ and a constant approximate
solution of size $k$ for the array, one can compute an exact solution for DTM
in time $O(k\log n)$. Just knowing the size of the approximate solution does
not suffice here; our algorithm requires random access to the elements of the
approximate solution as well.

Lemma 11, [restated informally]. Let $a$ be an array of length $n$ and $S$ be
a set of $k$ elements whose removal from $a$ makes $a$ increasing. One can
compute the distance to monotonicity of $a$ in time $O(k\log n)$.

The above algorithm, in addition to the 2-approximate solution, yields a
$1+\epsilon$ approximation block-based algorithm for DTM. Starting from an
array $a$ and provided access to a $2$-approximate solution, we set
$f(a)=\tilde{O}(k)$ where $k$ is the size of the approximate solution. Here,
$f,g,$ and $h$ do not depend on $n$ since the runtimes depend on the solution
size. See Section 3 for more information. Moreover, $g(a)=k\epsilon/2$ and
$h(a)=O(1)$. After computing an exact solution via the algorithm of Lemma 11
in the preprocessing phase, we keep reporting $d+i$ as an estimate for DTM for
the $i$’th operation where $d$ is the solution for the initial array. The
block-based algorithm then can be used to obtain a dynamic algorithm with
worst-case update time $O(\log^{2}n)$.

Theorem 14, [restated informally]. For any constant $\epsilon>0$, there exists
an algorithm for dynamic DTM whose worst-case update time is $O(\log^{2}n)$
and whose approximation factor is $1+\epsilon$.

Although our method is simple, it has a nice implication for classic
algorithms. We show that using Lemma 11, we can approximate DTM in time $O(n)$
within an approximation factor $1+\epsilon$ (a log is shaved from the runtime
by incurring a factor $1+\epsilon$ to the approximation guarantee). This
result is tight in two ways: i) Any constant factor approximation algorithm
for DTM has to make at least $\Omega(n)$ value queries to the elements of the
array to solve the case that the solution is either 0 or 1. ii) Any exact
solution which is comparison based or based on algebraic decisions trees has a
runtime of at least $\Omega(n\log n)$ [13, 31].

To achieve this, we first compute a 2-approximate solution for DTM in time
$O(n)$ (see Section C for more details). If the size of the solution is
smaller than $\sqrt{n}$, we use the algorithm of Lemma 11 to obtain an exact
solution in linear time. Otherwise, we use the algorithm of [29] to obtain a
$1+\epsilon$ approximate solution in time $O(n)$444The runtime of the
algorithm given in [29] is $\tilde{O}(n/d+\sqrt{n})$ when the solution size is
lower bounded by $d$..

##  3 From Amortized Update Time to Worst Case Update Time

The goal of this section is to show a reduction that simplifies the problem
with respect to worst-case time constraints. Ultimately, in our algorithms, we
prove that the update time of each operation is bounded in the worst case.
However, it is more convenient to allow for larger update times in some cases,
while keeping a bounded amortized update time. In this section, we prove that
if our algorithms adhere to a certain structure, then worst-case update time
reduces to amortized update time. Later in the section, we present a
motivating example to show how the reduction enables us to simplify the
proofs. In our example, we seek to design a $1+\epsilon$ approximation
algorithm for dynamic LIS with worst-case update time $\tilde{O}(\sqrt{n})$.

In our framework, we start with an array $a$ of size $n$ and our algorithm is
allowed to make a preprocessing of time $f(a)$. For the next $g(a)$ steps, the
processing time of each operation is bounded by $h(a)$ in the worst case.
After $g(a)$ steps, our algorithm is no longer responsible for the operations
and terminates. We refer to such an algorithm as block-based. Note $f(a)$,
$g(a)$, and $h(a)$ are not necessarily determined based only on the size $n$
of the array $a$. For example, in the algorithm of Section 6, the values of
these functions are proportional to the solution size for $a$, not $n$.
However, when these functions are only dependent on $n$, we may drop $a$ in
the notation and use $n$ instead. Functions $f,g,$ and $h$ should meet one
important property: after applying $g(a)$ arbitrary operations to an array $a$
and obtaining a new array $a^{\prime}$, $f(a^{\prime}),g(a^{\prime})$ and
$h(a^{\prime})$ should not change asymptotically. More specifically, although
the reduction holds when the values are within any constant factor, we assume
$1/2\leq f(a)/f(a^{\prime}),g(a)/g(a^{\prime}),h(a)/h(a^{\prime})\leq 2$. We
call this property relativity. We also assume without loss of generality that
$f,g,$ and $h$ are always lower bounded by a constant (say $20$) and when the
array size is constant, so are the values for $f(a),g(a),$ and $h(a)$.

We show in the following that a block-based algorithm $\mathcal{A}$ for LIS or
DTM with identifiers $\langle f,g,h\rangle$ can be used as a black box to
obtain a dynamic algorithm $\mathcal{A^{\prime}}$ with worst-case update time
$O(\max\\{h(a),f(a)/g(a)\\})$. The approximation factor of the algorithm is
preserved in this reduction. To show a use case of this technique, we provide
a simple analysis of a $(1+\epsilon)$-approximate dynamic algorithm for LIS
with worst-case update time $\tilde{O}(\sqrt{n})$.

######  Lemma 2.

Let $\mathcal{A}$ be a block-based algorithm with preprocessing time $f(a)$
that approximates dynamic LIS or dynamic DTM for up to $g(a)$ many steps with
worst-case update time $h(a)$. If $\langle f,g,h\rangle$ satisfies relativity
then there exists a dynamic algorithm $\mathcal{A}^{\prime}$ for the same
problem whose worst-case update time is bounded by
$O(\max\\{h(a),f(a)/g(a)\\})$ and whose approximation factor is the same as
$\mathcal{A}$.

###### Proof.

$\mathcal{B}_{1}$$a^{(1)}$$\mathcal{B}_{2}$$\mathcal{B}_{3}$$\dotsc$preprocessingupdating
two operations in each
step$g(a^{(1)})/10$$g(a^{(2)})/10$$a^{(2)}$$a^{(3)}$$1$$\frac{9g(a^{(1)})}{10}$$g(a^{(1)})$$\frac{9g(a^{(1)})}{10}+g(a^{(2)})$$\frac{9(g(a^{(1)})+g(a^{(2)}))}{10}$
Figure 6: The reduction is shown in this figure.

Figure 6 gives a pictorial depiction of the proof idea. We construct an
algorithm $\mathcal{A^{\prime}}$ in the following way: $\mathcal{A}^{\prime}$
uses algorithm $\mathcal{A}$ repeatedly. To distinguish between multiple
instances of $\mathcal{A}$, we add subscripts; the first time we use algorithm
$\mathcal{A}$ we call it $\mathcal{B}_{1}$. Every $\mathcal{B}_{i}$ is
basically a copy of the block-based algorithm $\mathcal{A}$ which is modified
slightly to execute the preprocessing part in multiple steps. We begin with
using our block-based algorithm $\mathcal{B}_{1}$ at step 1. At this point we
call the initial array (which is empty) $a^{(1)}$. Since the size of the array
is constant, so is the preprocessing time and therefore we can ignore it when
bounding the time complexity. For $g(a^{(1)})$ many steps, we use algorithm
$\mathcal{B}_{1}$ to preserve an approximate solution and from then on, we use
a separate algorithm for the rest of the operations, namely $\mathcal{B}_{2}$.
The construction of $\mathcal{B}_{2}$ is given below:

When $\mathcal{B}_{1}$ has gone $9/10$ of the way and is only responsible for
$g(a^{(1)})/10$ more operations, we initiate algorithm $\mathcal{B}_{2}$. Let
$a^{(2)}$ be the array at this point. $\mathcal{B}_{2}$ needs to run the
preprocessing step which requires $f(a^{(2)})$ many operations. This may not
be possible in a single step, therefore, we break the computation into
$g(a^{(1)})/20$ pieces and execute each piece in the next $g(a^{(1)})/20$
steps. Moreover, in the next $g(a^{(1)})/20$ steps operations that arrive
after the construction of $\mathcal{B}_{2}$ are processed: two operations in
each step. While this is happening, algorithm $\mathcal{B}_{1}$ processes the
operations and updates the solution size. When we reach $g(a^{(1)})/10$ many
steps after the construction of $\mathcal{B}_{2}$, algorithm $\mathcal{B}_{2}$
has already finished the preprocessing and all the operations that have
arrived so far are applied to it. This is exactly the time that
$\mathcal{B}_{1}$ terminates, and from then on, we use algorithm
$\mathcal{B}_{2}$ to process each operation.

Similarly, $\mathcal{B}_{3}$ is constructed when $\mathcal{B}_{2}$ has applied
$g(a^{(2)})9/10$ operations. This construction goes on as long as operations
arrive.

The correctness of $\mathcal{A}^{\prime}$ follows from that of $\mathcal{A}$.
Therefore, any approximation factor that $\mathcal{A}$ guarantees for us also
carries over to $\mathcal{A}^{\prime}$. For the update time, the construction
guarantees that at every time, at most two instances of algorithm
$\mathcal{A}$ are active. At every step, in each algorithm, we either perform
an operation or we are initializing the algorithm in which case the update
time is bounded by $O(\max\\{f(a)/g(a),h(a)\\})$.

One thing to keep in mind in the above argument is that because of relativity
the value of functions $f,g,$ and $h$ remain asymptotically the same during
two consecutive runs of algorithm $\mathcal{A}$. Thus, $g(a)$ is within a
constant factor for two consecutive runs of $\mathcal{A}$ and therefore
$f(a^{(i)})/g(a^{(i-1)})$ is asymptotically the same as
$f(a^{(i)})/g(a^{(i)})$. ∎

We emphasize that there is a constant-factor overhead in the update-time of
the reduction which is hidden in the $O$ notation.

To illustrate the effectiveness of our reduction, we bring a motivating
example to show how it simplifies the design of dynamic algorithms for LIS.

###  3.1 Warm Up: Block-based Algorithm for LIS

The reduction of Section 3 gives us a very convenient framework to design
dynamic algorithms for LIS and DTM. Here we bring a simple block-based
algorithm for dynamic LIS with approximation factor $1+\epsilon$ that results
in an algorithm with the same approximation factor and worst-case update time
$\tilde{O}(\sqrt{n})$.

Since in the following, functions $f,g$, and $h$ only depend on the size of
the array in this case, we write them in terms of $n$.

######  Lemma 3.

For any $\epsilon>0$, there exists a block-based algorithm for LIS with
approximation factor $1+\epsilon$, preprocessing time $f(n)=\tilde{O}(n)$ and
update time $h(n)=\tilde{O}(\sqrt{n})$ that maintains an approximate solution
to LIS for up to $g(n)=\sqrt{n}$ many operations.

###### Proof.

In the preprocessing phase, we first compute the longest increasing
subsequence in time $\tilde{O}(n)$. Let the solution size be $r$. Based on the
value of $r$, we consider two different strategies: If $r$ is already at least
$2\sqrt{n}/\epsilon$, in the next $\sqrt{n}$ steps, we do not make any changes
to the array and output $r-i$ after $i$’th operation. Since each operation
hurts the solution size by an additive factor of at most $1$, our solution is
always valid and has approximation factor $1+\epsilon$ throughout this
process.

Otherwise, we use the algorithm of Chen et al. [7] to update the solution in
every step. The setup cost for the algorithm of Chen et al. [7] is
$\tilde{O}(n)$ which can be executed in the preprocessing step (since this is
not explicitly mentioned in [7], we bring more details about their algorithm
in Appendix D). Moreover, the solution size is initially upper bounded by
$2\sqrt{n}/\epsilon$ and it can grow to at most $2\sqrt{n}/\epsilon+\sqrt{n}$
after $\sqrt{n}$ operations. Therefore, the update time remains
$\tilde{O}(\sqrt{n})$ in the worst case. ∎

Based on Lemma 2, a dynamic algorithm for LIS can be implemented with worst-
case update time $\tilde{O}(\sqrt{n})$ and approximation factor $1+\epsilon$.

######  Theorem 4.

[a corollary of Lemmas 2 and 3] For any constant $\epsilon>0$, there exists a
dynamic algorithm for LIS with approximation factor $1+\epsilon$ and update
time $\tilde{O}(\sqrt{n})$ in the worst case.

##  4 Grid Packing

This section is dedicated to a combinatorial problem which we call grid
packing. Definitions are given in Section 2 but for the sake of completeness
we restate them here. In this problem, we have a table of size $m\times m$.
Our goal is to introduce a number of segments on the table. Each segment
either covers a consecutive set of cells in a row or in a column. A segment
$A$ precedes a segment $B$ if every cell of $A$ is strictly higher than every
cell of $B$ and also every cell of $A$ is strictly to the right of every cell
of $B$. Two segments are non-conflicting, if one of them precedes the other
one. Otherwise, we call them conflicting. The segments we introduce can
overlap and there is no restriction on the number of segments or the length of
each segment. However, we would like to minimize the maximum number of
segments that cover each cell.

Figure 7: Segments are shown on the grid. The pair (black, orange) is
conflicting since the yellow cell (covered by the black segment) is on the
same row as the blue cell (covered by the orange segment). The following pairs
are non-conflicting: (green, black), (green, orange), (green, blue), (red,
orange), (red, blue), (black, blue).

After we choose the segments, an adversary puts a non-negative number on each
cell of the grid. The score of a subset of cells of the table would be the sum
of their values and the overall score of the table is the maximum score of a
path of length $2m-1$ from the bottom left corner to the top right corner. In
such a path, we always either move up or to the right.

The score of a segment is the sum of the numbers on the cells it covers. We
obtain the maximum sum of the scores of a non-conflicting set of segments. The
score of the table is an upper bound of on the score of any set of non-
conflicting segments. We would like to choose segments so that the ratio of
the score of the table and our score is bounded by a constant, no matter how
the adversary puts the numbers on the table. More precisely, we call a
solution $(\alpha,\beta)$-approximate, if at most $\alpha$ segments cover each
cell and it guarantees a $1/\beta$ fraction of the score of the table for us
for any assignment of numbers to the table cells.

$2$$0$$2$$3$$1$$1$$5$$0$$1$$0$$3$$0$$2$$1$$0$$1$ Figure 8: After we introduce
the segments (left figure), the adversary puts the numbers on the table
(middle figure). In this case, the score of the table is equal to $12$ (via
the path depicted on the right figure), and our score is equal to $9$ obtained
from two non-conflicting segments green and blue.

In this section, we prove the following theorem: For any grid $m\times m$ and
any $0<\kappa<1$, there exists a grid packing with guarantee
$(O(m^{\kappa}\log m),O(1/\kappa))$. That is, each cell is covered by at most
$O(m^{\kappa}\log m)$ segments and the ratio of the table’s score over our
score is bounded by $O(1/\kappa)$ in the worst case. This solution is
constructive and our proof also gives us the segments.

###  4.1 Array Packing

We first consider a useful sub-problem, array packing. Array packing is a one-
dimensional variant of grid packing, where we have an array of size $m$ and we
choose segments of consecutive cells in this array. Again segments can overlap
and there is no constraint on the number or size of the segments; after we fix
the segments an adversary puts non-negative numbers on the array cells; and
the score of a subset of the array cells would be the sum of their values.
Here we call a solution $(\alpha,\beta)$-approximate if no more than $\alpha$
segments cover each cell and for any interval $[x,y]$ of the array, there
exists a segment which completely lies in this interval with a score is at
least a $1/\beta$ fraction of the overall score of the interval.

Figure 9: A $(3,5)$-approximate solution is shown for an array packing problem
of size $10$. Blue segments cover three consecutive cells, red segments cover
two consecutive cells and each black segment covers a single cell. Each cell
is covered by at most $3$ segments. Also, one can prove that no matter how the
adversary puts the numbers on the array, for any interval, there is a segment
completely in that interval whose score is at least $1/5$ of the score of that
interval.

Here we show that when the array size is $m$, for any $0<\kappa<1$, there
exists a solution for array packing with approximation guarantee
$(O(m^{\kappa}\log m),O(1/\kappa))$. We then use this in a solution for grid
packing.

We construct two sets of segments in the following way: let $d$ be the largest
power of 2 such that $d^{2}\leq m^{\kappa}$. In the first set, for any $1\leq
i\leq d$ and any $1\leq j\leq m-i+1$ we introduce a segment starting from cell
$j$ and ending at cell $i+j-1$.

$d$$\vdots$$d$ Figure 10: In the first set, from each cell we introduce $d$
segments with lengths $1,2,\ldots,d$.

In the second set, for any integer $0\leq i\leq\log m$ and any $j$ divisible
by $2^{i}$ such that $j+d2^{i}-1\leq m$, we introduce a segment that spans the
interval $[j,j+d2^{i}-1]$.

$\dotsc$$d2^{i}$$2d2^{i}$$3d2^{i}$$4d2^{i}$$5d2^{i}$$2^{i}$$\vdots$$\dotsc$$\dotsc$$d$
Figure 11: In the second set, for each $i$, there is a segment of length
$d2^{i}$ starting from any cell whose starting point is divisible by $2^{i}$.
The distance between consecutive segments is $2^{i}$.

######  Lemma 5.

For any $m\geq 1$ and any $0<\kappa<1$ there exists a solution for the array
packing problem of size $m$ with approximation guarantee

$(O(m^{\kappa}\log m),O(1/\kappa)).$

###### Proof.

The solution is the union of the two sets of segments described above. The key
to showing it gives the required approximation is the following: For each
interval $[x,y]$ we can cover the entire interval with $O(1/\kappa)$ segments
that completely lie in the interval $[x,y]$. Therefore, no matter how the
adversary puts the numbers on the cells, the summation of the scores for such
segments is at least as much as the score of interval $[x,y]$ and thus one of
those segments has an $\Omega(\kappa)$ fraction of the score of interval
$[x,y]$. To show this, we cover the cells of the intervals in the following
way.

If $y-x<d$, then we can cover the entire interval with a single segment (of
the first type) and the proof is trivial. Otherwise, we only use the segments
of the second type in our covering. Let $q$ be the size of the largest segment
that completely lies in the interval $[x,y]$.

We start with an empty set $S_{\ell}$ and a pointer $p_{\ell}$ initially equal
to $x$. Each time we find a segment that starts in the range $[x,p_{\ell}]$
and ends in the range $[x,y]$. If many such segments exist, we choose the one
with the right-most ending point and in case of a tie, we break the tie
arbitrarily. We add the new segment to $S_{\ell}$ and continue the process by
increasing $p_{\ell}$ to the cell right after the new segment ends. We
continue this process so long as $p_{\ell}-x<q/d$

We repeat the same process but this time starting from $p_{r}=y$ and
proceeding backwards. Initially we set $S_{r}$ to be an empty set. Every time,
we find a segment that ends in range $[p_{r},y]$ and starts in range $[x,y]$.
Similarly, when multiple options are available, we choose the one whose
starting point is the smallest. We add the new segment to $S_{r}$ and update
$p_{r}$ to be the right-most cell not covered by the new segment. We terminate
this process when $y-p_{r}\geq q/d$.

Obviously segments in $S_{\ell}\cup S_{r}$ cover both intervals
$[x,p_{\ell}-1]$ and $[p_{r}+1,y]$. If $p_{r}<p_{\ell}$ then the entire
interval $[x,y]$ is covered. Otherwise, we can add two more segments of size
$q$ to fill the gap. More precisely, we add the left-most and right-most
segments of length $q$ that lie completely in the interval $[x,y]$. The
analysis is based on the following property of our construction: the distance
between consecutive segments of length $q$ is bounded by $q/d$. Thus, after
putting such segments on the interval $[x,y]$, each cell is covered except the
ones whose distance to one of the end points is smaller than $q/d$. However,
segments of sets $S_{\ell}$ and $S_{r}$ cover those cells.

We show that $|S_{\ell}|,|S_{r}|\leq O(1/\kappa)$. To this end, we prove that
every time we add a new segment to $S_{\ell}$, the size of the new segment is
at least $d$ times larger than the size of the previous segment we added to
$S_{\ell}$. The reason is the following: let $l$ be the length of the segment
we add to $S_{\ell}$ at some point. This means that after adding this segment
to $S_{\ell}$ we have $p_{\ell}\geq x+l$. $l$ is a power of $2$ since we only
use the segments of the second type. Moreover, one cell in this range is
divisible by $l$ which means that it is the starting point of another segment
of length $dl$. Thus the next segment that we add to $S_{\ell}$ has a length
at least $dl$ which is $d$ times larger than the current one. Therefore, the
size of $|S_{\ell}|$ is bounded by $\log_{d}m=O(1/\kappa)$. The same also
holds for $S_{r}$.

$x$$y$$q$$q$$\geq q/d$$\geq q/d$$<q/d$$<q/d$ Figure 12: Green parts are
covered with segments in $S_{\ell}$ and blue parts are covered by segments in
$S_{r}$. Two segments of length $q$ cover the rest of the elements.

All that remains is to show that each cell of the array is covered by at most
$O(m^{\kappa}\log m)$ different segments. In the first set, the length of each
segment is bounded by $d$ and therefore there are at most $d^{2}$ different
combinations for the starting and ending cells of the intervals that cover a
particular cell. Since $d^{2}\leq m^{\kappa}$, this guarantee is met by the
first set of segments. For the second set, notice that there are at most
$O(\log m)$ distinct segment sizes. Moreover, each cell is covered by at most
$d$ segments of a particular size. Thus, each cell is covered by at most
$O(d\log m)$ different segments of the second set which is bounded by
$O(m^{\kappa}\log m)$.

∎

###  4.2 An $(O(m^{\kappa}\log m),O(1/\kappa))$-approximate Solution for Grid
Packing

We provide a reduction from grid packing to array packing. The intuition
behind the reduction is given below: Let us fix a path from the bottom-left to
the top-right of the array. We can divide the cells of the path into some
disjoint vertical and horizontal intervals as show in Figure 13. In this
decomposition, all the row-intervals are non-conflicting and all the column-
intervals are also non-conflicting (row-intervals and column-intervals may be
conflicting).

Figure 13: Each path from bottom-left to top-right is divided into disjoint
row-intervals or column-intervals. Row intervals are shown with orange and
column intervals are shown with blue. All row intervals are non-conflicting
and all column-intervals are also non-conflicting.

For any path and any combination of numbers on the cells of the path, either
the sum of the numbers on the row-intervals or the sum of numbers on the
column intervals is at least a $1/2$ fraction of the total sum of the numbers
on the path. Based on this, we can reduce grid packing to array packing in the
following way.

######  Theorem 6.

For any $0<\kappa<1$, the grid packing problem on an $m\times m$ grid admits
an $(O(m^{\kappa}\log m),O(1/\kappa))$-approximate solution.

###### Proof.

We treat every row and every column of the grid as an array of length $m$ and
construct an $(O(m^{\kappa}\log m),O(1/\kappa))$-approximate solution of the
array packing problem for that row or column (Lemma 5). With this
construction, every cell is covered by at most $O(m^{\kappa}\log m)$ segments,
because every cell is covered by at most $O(m^{\kappa}\log m)$ horizontal
segments and every cell is covered by at most $O(m^{\kappa}\log m)$ vertical
segments, so the total number of segments covering each cell is bounded by
$O(m^{\kappa}\log m)$.

After the adversary puts the numbers on the cells of the grid, the score of
the grid equals the largest score of a path of the length $2m-1$ that starts
from the bottom left corner and moves to the top right corner. As mentioned
previously, we can divide the cells of such a path into non-conflicting row
intervals and non-conflicting column intervals. The score of either the row
intervals or column intervals is at least half the score of this path. Let it
be the row intervals without loss of generality. By Lemma 5, there is one
segment in each row that approximates the score of the corresponding interval
within a factor $O(1/\kappa)$ and fits completely within that interval. Since
all the row-intervals are non-conflicting, these segments are non-conflicting,
and the score of those segments is at least an $O(1/\kappa)$ fraction of the
score of the row intervals, which is at least $1/2$ of the score of the grid.
This completes the proof. ∎

##  5 Constant Factor Approximation for LIS with Update Time
$\tilde{O}(n^{\epsilon})$

In this section, we show that for any constant $\epsilon>0$, there is a
dynamic algorithm for LIS that loses only a constant factor in the
approximation (where the constant depends on $\epsilon$) and guarantees an
update time bounded by $\tilde{O}(n^{\epsilon})$. Our algorithm is based on
the grid packing technique explained in Section 4.

We begin by explaining a simple algorithm for dynamic LIS where the
approximation factor is constant and the update time is close to
$\tilde{O}(n^{2/3})$. This result is weaker than what we give in Section 3
both in terms of update time and approximation factor, but we show this new
technique can be extended to obtain the result for any $\epsilon>0$ above.

We remind the reader that an exact algorithm with worst-case update time
$\tilde{O}(n)$ is trivial; we compute the LIS from the scratch after each
operation arrives. We call this algorithm $\mathcal{A^{\prime}}_{0}$555It will
be clear to the reader later in the section why we use such an unconventional
notation for this algorithm.. From $\mathcal{A^{\prime}}_{0}$, we make a
block-based algorithm $\mathcal{A}_{1}$ and then turn it into an algorithm
$\mathcal{A^{\prime}}_{1}$ with worst-case update time
$\tilde{O}(n^{2/3+\kappa})$ for a small enough $\kappa>0$.

In our block-based algorithm, we begin by an array $a$ of length $n$. Map the
elements of $a$ onto the 2D plane by creating a point $(i,a_{i})$ for every
element of the array. Recall that we assume the elements are distinct but
there is no bound on their values. Define $m=n^{1/3}$ and construct a grid in
the following way: draw $m-1$ horizontal lines that divide the plane into
parts of as equal size as possible with respect to the number of points
included in each part. If $n$ is not divisible by $m$, some parts may have one
more point than other parts. Similarly, we draw $m-1$ vertical lines that
separate the plane into $m$ parts each having either $\lfloor n/m\rfloor$ or
$\lceil n/m\rceil$ points. This gives an $m$ by $m$ grid, with each grid cell
corresponding to a “rectangle” in the 2D plane.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$(7,2,4\
|\ 1,9,6\ |\ 3,5,8)$$(7,2,4\ |\
1,9,\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},6\
|\ 3,5,8)$ Figure 14: An example for adding an element to the array.

Our block-based algorithm works in the following way: fix a $0<\kappa<1$ and
construct a grid packing solution with approximation $(O(m^{\kappa}\log
m),O(1/\kappa))$ for the $m$ by $m$ grid. Each element of the array lies in
exactly one cell of the grid and corresponds to all segments that cover that
cell. Next for each segment in the solution of grid packing, we construct a
separate instance of the LIS problem that maintains a solution for the LIS of
the corresponding elements.

Each time an operation arrives, we update the solution for the corresponding
segments. Let us be more specific about this. Initially, $m-1$ vertical lines
divide the array into chunks of size roughly $n/m$. As operations arrive, the
elements are shifted to the left or to the right (their indices are updated).
Each vertical line can be thought of as a separator between two consecutive
elements that is also shifted to the left or to the right when elements are
added or removed. Thus, although the vertical lines move, each element which
is inserted or deleted lies between two thresholds and corresponds to a unique
column of the grid. The corresponding row is uniquely determined by the
horizontal lines (those lines remain unchanged). Thus, every element insertion
or deletion affects only one cell of the grid which is covered by a bounded
number of segments. When the size of the LIS is desired, we run a dynamic
program and find a subset of non-conflicting set of segments whose total
solution size is maximized. We show that this gives us approximation factor
$O(1/\kappa)$ for the LIS of the array. Our algorithm is responsible for up to
$g(n)=n^{2/3}$ many operations.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$\langle
7,2,4\ |\ 1,9,6\ |\ 3,5,8\rangle$$\langle 7,2,4\ |\ 1,6\ |\ 3,5,8\rangle$
Figure 15: An example for removing an element from the array.

######  Lemma 7.

Let $0<\kappa<1$ be an arbitrarily small constant used for the solution of
grid packing. $\mathcal{A}_{1}$ is a block-based algorithm for dynamic LIS
with approximation factor $O(1/\kappa)$ whose preprocessing time is
$\tilde{O}(n^{1+\kappa})$ and whose update time is
$\tilde{O}(n^{2/3+\kappa})$. Moreover, $\mathcal{A}_{1}$ runs for $n^{2/3}$
many steps.

###### Proof.

We first prove that the preprocessing time of $\mathcal{A}_{1}$ is
$\tilde{O}(n^{1+\kappa})$. It takes time $\tilde{O}(n)$ to sort the numbers
and draw the grid lines. Also, the runtime for constructing the solution for
grid packing is $\tilde{O}(m^{2+\kappa})$, which is smaller than
$\tilde{O}(n)$. Every cell of the grid is covered by at most
$\tilde{O}(m^{\kappa})$ different segments. We construct a separate LIS
instance for every segment. Each grid cell appears in at most
$\tilde{O}(m^{\kappa})$ segments. Therefore, every element of the array in
included in in at most $\tilde{O}(m^{\kappa})$ LIS instances. Thus, the total
size of all the instances combined is bounded by $\tilde{O}(nm^{\kappa})$ and
thus finding an LIS for each segment takes time $\tilde{O}(nm^{\kappa})$ in
total. Since $m=n^{1/3}$ the preprocessing time is bounded by
$\tilde{O}(n^{1+\kappa/3})=\tilde{O}(n^{1+\kappa})$.

The total number of points in every column, or every row of the grid is
bounded by $\lceil n/m\rceil=O(n^{2/3})$. Thus, the size of the LIS instance
for each segment is also bounded by $O(n^{2/3})$. Since we run the algorithm
for at most $O(n^{2/3})$ many steps, the sizes of the LIS instances remain
bounded by $O(n^{2/3})$ even if we add more numbers to them in the next
$O(n^{2/3})$ many operations.

When a new operation arrives, this only affects one cell of the grid which we
can find using its position and its value. We update all the corresponding
segments that cover that cell. Their count is bounded by
$\tilde{O}(m^{\kappa})\leq\tilde{O}(n^{\kappa})$. Moreover, each one we can
update in time $\tilde{O}(n^{2/3})$ since the problem size for each segment is
bounded by $O(n^{2/3})$. Every time the size of the LIS is desired, we run a
DP in time $\tilde{O}(m^{2+\kappa})$ and find a solution that can be
constructed using non-conflicting segments. The size of the LIS for each
segment is available in time $O(1)$. Thus, the runtime for approximating the
LIS is bounded by $\tilde{O}(m^{2+\kappa})\leq\tilde{O}(n^{2/3+\kappa})$.
Therefore, the update time $h(n)$ is bounded by $\tilde{O}(n^{2/3+\kappa})$
for every operation.

For the dynamic program, we define an $m\times m$ table $D$ such that
$D[i][j]$ denotes the solution for any subset of non-conflicting segments in
the first $i$ rows and the first $j$ columns of the grid. Obviously
$D[i][j]\geq D[i-1][j],D[i][j-1]$. Thus, when computing the value for
$D[i][j]$, we start by assigning $\max\\{D[i-1][j],D[i][j-1]\\}$ to it. Next,
for any segment that ends at cell $(i,j)$, we update $D[i][j]$ as

$D[i][j]=\max\\{D[i][j],D[i^{\prime}-1][j^{\prime}-1]+w\\}$

where $(i^{\prime},j^{\prime})$ are coordinates of the bottom-left corner of
the segment and $w$ is the length of its LIS. The total runtime of this
algorithm is asymptotically equal to the number of segments on the grid.

Finally, we show that this gives us an $O(1/\kappa)$-approximate solution for
the LIS of the entire array. For any point in time, fix an arbitrary solution
of the longest increasing subsequence for the array at that time. Assume that
the numbers the adversary puts on the cells of the grid are the contributions
of the cells to the fixed longest common subsequence. This way, the score of
the grid is exactly equal to the size of the longest increasing subsequence.

In addition to the above, the score of every segment is a lower bound on the
LIS of the elements for that segment. Thus, by the guarantee of the grid
packing solution, the solution we obtain by appending the solutions of non-
conflicting segments is definitely an $O(1/\kappa)$ approximate solution for
the score of the grid which is the size of the solution. Finally, the validity
of our solution follows from the fact that since all the segments are non-
conflicting, then we can combine their partial solutions and that gives us a
valid increasing subsequence.

Keep in mind that when we add elements to or remove elements from the array,
the indices of the numbers change. Thus, we need to also update the
coordinates of the vertical lines. This can be done similarly to the way we
update the indices of the array elements. Therefore, this does not add
computational difficulty as all we need to know for each new operation is
which column of the grid this operation applies to and which row of the grid
is affected by the new operation. Also, for edge cases (when the left most or
right most element of a column is removed or added), we have a choice of which
column we add the new points to. In any case, the solution we find preserves
the approximation.

∎

One thing to note about the algorithm of Lemma 7 is that by setting $\kappa$
arbitrarily close to $0$, we can obtain a update time close to
$\tilde{O}(n^{2/3})$. By Lemma 2, algorithm $\mathcal{A}_{1}$ can be turned
into an algorithm $\mathcal{A^{\prime}}_{1}$ with the same approximation
factor but worst-case update time $\tilde{O}(n^{2/3+\kappa})$. Although
$\mathcal{A^{\prime}}_{1}$ has an approximation factor of $O(1/\kappa)$, its
update time is $\tilde{O}(n^{1/3-\kappa})$ times smaller than that of
$\mathcal{A^{\prime}}_{0}$. Thus, our approach to improve the overall update
time is to replace $\mathcal{A^{\prime}}_{0}$ by $\mathcal{A^{\prime}}_{1}$ to
obtain a faster (but worse in terms of approximation factor) algorithm.

######  Lemma 8 (as a corollary of Lemmas 7 and 2).

For any $0<\kappa<1$, there exists a dynamic algorithm for LIS with worst case
update time $\tilde{O}(n^{2/3+\kappa})$ and approximation factor
$\tilde{O}(1/\kappa)$.

It is not hard to see that one can recurse on the above idea to improve the
update time. This comes however, at the expense of a larger approximation
factor. We prove in Theorem 9 that, similar to what we did for Lemma 7, one
can devise an algorithm with worst-case update time $\tilde{O}(n^{\epsilon})$
with approximation factor $O((1/\epsilon)^{O(1/\epsilon)})$ for any
$\epsilon>0$.

######  Theorem 9.

For any constant $\epsilon>0$, there exists an algorithm for dynamic LIS whose
worst-case update time is $\tilde{O}(n^{\epsilon})$ and whose approximation
factor is $O((1/\epsilon)^{O(1/\epsilon)})$.

###### Proof.

Dynamic | worst-case | approximation
---|---|---
algorithm | update time | factor
$\mathcal{A^{\prime}}_{0}$ | $\tilde{O}(n)$ | 1
$\mathcal{A^{\prime}}_{1}$ | $\tilde{O}(n^{2/3+\kappa})$ | $O(1/\kappa)$
$\mathcal{A^{\prime}}_{2}$ | $\tilde{O}(n^{1/2+\kappa})$ | $O(1/\kappa^{2})$
$\mathcal{A^{\prime}}_{3}$ | $\tilde{O}(n^{2/5+\kappa})$ | $O(1/\kappa^{3})$
⋮ | ⋮ | ⋮
$\mathcal{A^{\prime}}_{k}$ | $\tilde{O}(n^{\frac{2}{k+2}+\kappa})$ | $O(1/\kappa)^{k}$
Table 2: Guarantees of the dynamic solutions are shown in this figure. block-based | $m$ | $f(n)$ | $g(n)$ | $h(n)$ | approximation
---|---|---|---|---|---
algorithm |  |  |  |  | factor
$\mathcal{A}_{1}$ | $n^{1/3}$ | $\tilde{O}(n^{1+\kappa})$ | $n^{2/3}$ | $\tilde{O}(n^{2/3+\kappa})$ | $O(1/\kappa)$
$\mathcal{A}_{2}$ | $n^{1/4}$ | $\tilde{O}(n^{1+\kappa})$ | $n^{3/4}$ | $\tilde{O}(n^{1/2+\kappa})$ | $O(1/\kappa^{2})$
$\mathcal{A}_{3}$ | $n^{1/5}$ | $\tilde{O}(n^{1+\kappa})$ | $n^{4/5}$ | $\tilde{O}(n^{2/5+\kappa})$ | $O(1/\kappa^{3})$
⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮
$\mathcal{A}_{k}$ | $n^{\frac{1}{k+2}}$ | $\tilde{O}(n^{1+\kappa})$ | $n^{\frac{k+1}{k+2}}$ | $\tilde{O}(n^{\frac{2}{k+2}+\kappa})$ | $O(1/\kappa)^{k}$
Table 3: Guarantees of the block-based solutions are shown in this figure. We
assume that the length of the initial array $a$ for the block-based algorithm
is $n$.

The proof is by induction. Let us fix a constant $0<\kappa<1$ that is used for
all recursions. For any $k\geq 1$, our aim is to design a dynamic algorithm
for LIS with approximation factor $O((1/\kappa)^{k})$ and worst-case update
time $\tilde{O}(n^{\frac{2}{k+2}+\kappa})$. We call such an algorithm
$\mathcal{A}^{\prime}_{k}$. The base case is for $k=0$ for which we already
know a solution $\mathcal{A}^{\prime}_{0}$. We also strengthen our hypothesis:
If instead of starting from an empty array, we start with an array of length
$n$, our algorithm needs a preprocessing time of $\tilde{O}(n^{1+\kappa})$.

Let us assume that for $k\geq 1$, $\mathcal{A}^{\prime}_{k-1}$ with desirable
guarantees is available and the goal is to design $\mathcal{A}^{\prime}_{k}$.
To this end, we first make a block-based algorithm $\mathcal{A}_{k}$ with the
following properties: For an initial array $a$ of length $n$, we set
$f(n)=n^{1+\kappa}$, $g(n)=n^{\frac{k+1}{k+2}}$, and
$h(n)=\tilde{O}(n^{\frac{k+1}{k+2}+\kappa})$. Similar to what we did in Lemma
7, we map every element of the initial array $a$ onto the 2D plane by putting
a point $(i,a_{i})$ for every element. We set $m=n^{\frac{1}{k+2}}$ and divide
the plane into an $m\times m$ grid, such that in each row and in each column
there are at most $\lceil n/m\rceil$ points. Moreover, we construct a grid
packing solution for the $m\times m$ grid with approximation guarantee
$(\tilde{O}(m^{\kappa}),O(1/\kappa))$. Next, for each segment we initiate an
LIS instance that will be solved with algorithm $\mathcal{A}^{\prime}_{k-1}$.

The preprocessing time consists of two parts: (i) constructing the solution to
grid packing in time $\tilde{O}(m^{2+\kappa})$ and (ii) constructing an
initial solution for each segment. Since the problem size for each segment is
bounded by $n/m$ and every element appears in at most $\tilde{O}(m^{\kappa})$
segments and the initialization time for $\mathcal{A}^{\prime}_{k-1}$ is
$\tilde{O}(n^{1+\kappa})$ this can be bounded by
$\tilde{O}(m^{\kappa}n(n/m)^{\kappa})=\tilde{O}(n^{1+\kappa})$. Thus, the
total preprocessing time is bounded by

$\tilde{O}(m^{2+\kappa}+n^{1+\kappa})=\tilde{O}(n^{1+\kappa}).$

By the construction of the grid, the size of the problem for each segment is
bounded by $O(n/m)=O(n^{\frac{k+1}{k+2}})$. Also, since
$g(n)=O(n^{\frac{k+1}{k+2}})$, the size of the problem instance corresponding
to each segment remains in this range throughout the $g(n)$ many steps. Each
time an operation arrives, we update the solution for $\tilde{O}(m^{\kappa})$
many segments each in time $\tilde{O}((n/m)^{\frac{2}{k+1}+\kappa})$ (recall
that we use $\mathcal{A}^{\prime}_{k-1}$ for the solution of the segments).
Thus, the update time is bounded by

$\displaystyle\tilde{O}(m^{\kappa}(n/m)^{\frac{2}{k+1}+\kappa})$
$\displaystyle=\tilde{O}(n^{\kappa}(n/m)^{\frac{2}{k+1}})$
$\displaystyle=\tilde{O}(n^{\kappa}(n^{\frac{k+1}{k+2}})^{\frac{2}{k+1}})$
$\displaystyle=\tilde{O}(n^{\kappa}n^{\frac{2}{k+2}})$
$\displaystyle=\tilde{O}(n^{\frac{2}{k+2}+\kappa}).$

Moreover, in order to find an approximate solution for LIS using non-
conflicting segments, we need to run a DP in time
$\tilde{O}(m^{2+\kappa})=\tilde{O}(n^{\frac{2+\kappa}{k+2}})=\tilde{O}(n^{\frac{2}{k+2}+\kappa})$.
Thus, the overall worst-case update time is equal to
$h(n)=\tilde{O}(n^{\frac{2}{k+2}+\kappa})$.

Finally, the approximation factor increases by a multiplicative factor of
$O(1/\kappa)$ in each level of recursion. Thus, the approximation factor of
$\mathcal{A}_{k}$ is bounded by $O((1/\kappa)^{k})$. Using Lemma 2, we can the
turn block-based algorithm $\mathcal{A}_{k}$ into an algorithm for LIS with
worst-case update time $\tilde{O}(n^{\frac{2}{k+2}+\kappa})$. Finally, since
we are constructing $\mathcal{A}^{\prime}_{k}$ from a block-based algorithm
with preprocessing time $\tilde{O}(n^{1+\kappa})$, if we start from an array
$a$ of length $n$, we need a preprocessing time of $\tilde{O}(n^{1+\kappa})$
which is another condition of the hypothesis.

Now, for a fixed $\epsilon>0$, we set $\kappa=\epsilon/2$ and $k=\lceil
4/\epsilon\rceil$. Thus, the worst-case update time of the algorithm would be
bounded by

$\displaystyle\tilde{O}(n^{\frac{2}{k+2}+\kappa})$
$\displaystyle\leq\tilde{O}(n^{\frac{2}{k}+\kappa})$
$\displaystyle=\tilde{O}(n^{\frac{2}{k}+\epsilon/2})$
$\displaystyle\leq\tilde{O}(n^{\epsilon/2+\epsilon/2})$
$\displaystyle=\tilde{O}(n^{\epsilon})$

which is desired. Also, the approximation factor would be bounded by
$O((1/\epsilon)^{O(1/\epsilon)})$. ∎

##  6 $1+\epsilon$ Approximation for DTM

In this section, we give a dynamic algorithm for DTM with approximation factor
$1+\epsilon$ and update time $O(\log^{2}n)$. If access to the elements of the
array is provided in time $O(1)$, the update time improves to $O(\log n)$.
However, since we use a balanced binary tree for the elements, there is an
additional $O(\log n)$ overhead for the update time. We explain the algorithm
in four steps. In the first step, we present a simple algorithm that obtains
an approximation factor of $2$ with the same update time. Next, in Step 2, we
show how a $2$-approximate solution can be used to obtain an exact solution in
time $O(k^{2}\log n)$ when the solution size is bounded by $k$. In the third
step, we improve the runtime of the same algorithm to $O(k\log n)$. Finally,
we show in the last step that such an algorithm along with the $2$-approximate
solution in time $O(\log^{2}n)$ gives us a $1+\epsilon$ approximate solution
with update time $O(\log^{2}n)$.

###  6.1 A $2$-approximate Solution for DTM

Similar to previous work [17], we call a pair $(a_{i},a_{j})$ an inversion, if
$i<j$ but $a_{i}>a_{j}$. The heart of the analysis is that a maximal set of
disjoint inversion pairs is a 2-approximate solution for DTM. We first
formally give a proof to this claim and next show how such a maximal set can
be maintained with $O(\log^{2}n)$ update time.

######  Observation 1.

Let $a=\langle a_{1},a_{2},\ldots,a_{n}\rangle$ be an array of length $n$ and
$S=\\{(a_{\alpha_{1}},a_{\beta_{1}}),(a_{\alpha_{2}},a_{\beta_{2}}),\ldots\\}$
be a maximal set of disjoint inversions of $a$. Then we have

$|S|\leq\mathsf{DTM}(a)\leq 2|S|.$

###### Proof.

Since every pair $(a_{\alpha_{i}},a_{\beta_{i}})$ is an inversion, then any
solution for DTM should remove one element from each pair which implies
$\mathsf{DTM}(a)\geq|S|$. On the other hand, if we remove all the $2|S|$
elements of $S$ from $a$, the remaining subsequence is increasing since $S$ is
maximal and thereby there is no inversion in the remaining elements. This
implies that $\mathsf{DTM}(a)\leq 2|S|$. ∎

Based on Observation 1, our 2-approximate algorithm maintains a maximal set of
disjoint inversions with update time $O(\log^{2}n)$.

######  Lemma 10.

There exists a $2$-approximate solution for $\mathsf{DTM}$ with update time
$O(\log^{2}n)$.

###### Proof.

Our algorithm maintains a maximal collection of disjoint inversion pairs,
namely $S$. In addition to this, both the elements used in this collection and
the elements not used in this collection are stored in a balanced tree666Red
black tree could be one implementation. that allows for search, insertion, and
deletion in logarithmic time. We refer to the tree containing the elements of
$S$ with $T_{S}$ and the tree containing other elements by $T_{N}$.

Whenever a new element $a_{i}$ is inserted into the array, we first check if
it makes an inversion with the elements of $T_{N}$. Notice that these elements
are increasing in the order of their indices since there is no inversion
between them. Thus, in order to verify whether $a_{i}$ makes an inversion with
any element of $T_{N}$, we just need to compare that to the largest $a_{j}\in
T_{N}$ which is smaller than $a_{i}$ or the smallest $a_{j}\in T_{N}$ which is
larger than $a_{i}$. Both of these two operations can be done in time
$O(\log^{2}n)$ (the exponent of $\log$ is 2 since it takes time $O(\log n)$
for us to get the value of the $i$’th element of the array). If an inversion
is detected, we add it to $S$ and update $T_{N}$ and $T_{S}$ accordingly.
Otherwise, we add $a_{i}$ into $T_{N}$.

Removing an element is also strait-forward. If the element belongs to $T_{N}$,
then no action is required other than updating $T_{N}$. Otherwise, after
removing $a_{i}$, we have to be careful about the element which made an
inversion with $a_{i}$ previously. That can be handled in time $O(\log^{2}n)$
similar to adding new elements. We check if it makes an inversion with the
elements of $T_{N}$ and update both $T_{N}$ and $T_{S}$ accordingly. All these
operations can be done in time $O(\log^{2}n)$. ∎

###  6.2 From $2$-approximate Solution to an Exact Solution

We show that a $2$-approximate solution for DTM can be used to obtain an exact
solution. In fact, this idea carries over to any constant approximate solution
but for simplicity we state it only for $2$-approximate solutions. Let us
denote the size of the $2$-approximate solution by $k$. This way, we know that
the optimal solution is in range $[k/2,k]$.

We first construct a graph $G$ in the following way. Every element of the
array becomes one vertex of $G$ and we put an edge between two vertices if
their corresponding elements in $a$ make an inversion. This way, finding
distance to monotonicity of array $a$ is equivalent to finding the smallest
vertex cover of $G$.

Let set $S$ be all the elements that are removed from the array in our
$2$-approximate solution (thus we have $|S|=k$). We refer to the vertices of
$G$ corresponding to set $S$ by $v_{1}$, $v_{2}$, $\ldots$, $v_{k}$. The key
observation is that every edge of the graph is incident to at least one vertex
$v_{i}$ otherwise $\cup_{i\in[k]}\\{v_{i}\\}$ would not be a valid vertex
cover.

We call a vertex of the graph low-degree if its degree is upper bounded by $k$
and high-degree otherwise. Based on this, we divide the vertices corresponding
to set $S$ into two disjoint sets $L$ and $H$ containing the low-degree and
high-degree vertices. All vertices of $H$ have to be included in the optimal
solution otherwise all their neighbors should be included and their number is
more than $k$. Thus, we can include those vertices in our solution and remove
them from the graph (this includes their incident edges too).

For each remaining edge of the graph, one end point is in $L$. Moreover, the
degrees of the vertices in $L$ are bounded by $k$. Thus, the total number of
remaining edges in the graph is bounded by $k^{2}$. Therefore, apart from at
most $2k^{2}$ vertices, all the other vertices are isolated and definitely do
not contribute to the vertex cover. Thus, we need to solve the problem for
$O(k^{2})$ many elements. This is equivalent to finding DTM for $O(k^{2})$
many vertices which can be solved in time $O(k^{2}\log n)$. There is an
additional $O(\log n)$ overhead involved if access to each element requires
time $O(\log n)$.

######  Lemma 11.

Let $a$ be an array of length $n$ and $S$ be a set of $k$ elements whose
removal from $a$ makes $a$ increasing. Provided oracle access to the elements
of $a$, one can compute the distance to monotonicity of $a$ in time
$O(k^{2}\log n)$.

###### Proof.

The correctness of the algorithm is already discussed. Here we just show a
bound on the runtime. Since set $S$ is given, we just need to compute the
degree of each vertex. There are $k$ elements in set $S$ so detecting the
edges between them can be done in time $O(k^{2})$. Moreover, for every vertex
$v_{i}$ corresponding to the elements of $S$, detecting its edges to the rest
of the elements can also be done in time $O(\log n)$ since a binary search
suffices for that purpose. Therefore, the total runtime is $O(k^{2}\log n)$. ∎

###  6.3 Exact Solution in Quasi-linear Time

We show that the runtime of the algorithm of Section 6.2 can be improved to
quasi-linear. Let us for simplicity divide the element of the array into two
sets $S$ and $N$. Set $S$ corresponds to the elements of the approximate
solution (whose removal makes the array increasing) and set $N$ contains the
rest of the elements. Obviously, set $N$ is increasing otherwise $S$ would not
be a valid solution to distance to monotonicity. The key to our improvement is
the following observation:

######  Observation 2.

Let $a_{i}<a_{j}<a_{k}$ be three elements of set $N$ and $a_{l}$ be an element
of set $S$. If both $(a_{i},a_{l})$ and $(a_{k},a_{l})$ are inversions, then
$(a_{j},a_{l})$ is also an inversion.

###### Proof.

Notice that since we have $a_{i}<a_{j}<a_{k}$ and all three are in $N$, then
we can infer that $i<j<k$. On the other hand, since both $(a_{i},a_{l})$ and
$(a_{k},a_{l})$ are inversions, then either both $l<i$ and $a_{l}>a_{k}$ hold
or both $l>k$ and $a_{l}<a_{i}$ hold. In either case, $(a_{j},a_{l})$ makes an
inversion. ∎

Observation 2 shows that any element of $S$ makes an inversion with an
interval of the elements in $N$. This implies an important consequence: Label
each element $a_{i}\in N$ with a set of elements $I(a_{i})\subseteq S$ such
that for each element $a_{j}\in I(a_{i})$, pair $(a_{i},a_{j})$ makes an
inversion. Based on Observation 2 we can prove that the total number of
distinct labels in $N$ is bounded by $2|S|+1$.

######  Lemma 12.

For each element $a_{i}\in N$, define its label by $I(a_{i})\subseteq S$ where
$I(a_{i})$ contains all elements of $S$ that make an inversion with $a_{i}$.
Then we have:

$|\bigcup_{a_{i}\in N}\\{I(a_{i})\\}|\leq 2|S|+1.$

###### Proof.

For each element $a_{j}\in S$ that makes an inversion with an element of $N$
define two thresholds $\alpha$ and $\beta$ where $\alpha$ is the smallest
element of $N$ that makes an inversion with $a_{j}$ and $\beta$ is the
smallest element of $N$ larger than $\alpha$ that does not make an inversion
with $a_{j}$. Due to Observation 2, an element of $N$ makes an inversion with
$a_{j}$ if and only if its value is at least $\alpha$ and smaller than
$\beta$. The total number of thresholds for all elements of $S$ is at most
$2|S|$. Moreover if two elements of $N$ are not separated by any threshold,
then their labels are the same. Thus, the total number of distinct labels is
bounded by $2|S|+1$. ∎

$N$$S$ Figure 16: Inversions between the elements of $S$ and $L$ are shown in
this figure. Elements of $N$ with equal labels are colored similarly.

Lemma 12 is important from an algorithmic point of view because of the
following: if two elements have the same label (and thus the same set of
conflicting elements in $S$), either they both contribute to the optimal
solution (removed from the array) or they both remain in the array. Thus, one
can merge these elements and make a larger element in the array that
represents both of them. More generally, for each label, if we merge all the
element attributed to that label and make a single element out of them (with a
larger size), the size of the optimal solution remains unchanged. Since the
total number of labels is bounded by $2|S|+1$ then this transformation leaves
us with $2|S|+1$ elements and we only need to solve the problem for them. This
can be done in time $O(k\log n)$ as shown in Lemma 13. We note that in the
above, we assume random access to the elements of the array is provided in
time $O(1)$.

######  Lemma 13.

Given query access to an array $a$ of length $n$ and a $2$-approximate
solution for distance to monotonicity of $a$ with size $k$, one can find an
exact solution for distance to monotonicity in time $O(k\log n)$.

###### Proof.

The algorithm and its correctness is outlined above. Here we just explain the
runtime. Since the elements of $N$ are stored in a balanced tree data
structure, for each element of $S$ we can find in time $O(\log n)$ which
interval of the elements of $N$ makes an inversion with it. This takes a total
runtime $O(k\log n)$. Next, we sort all the intervals based on them and merge
elements of $N$ whose labels are the same. We refer to these merged elements
as super elements. The value of a super element can be equal to the value of
an arbitrary element which is used in its construction.

After constructing the super elements in time $O(k\log n)$ the size of the
problem reduces to $O(k)$. However, patience sorting does not solve this
problem since super elements have weights. In other words, removing a super
element incurs a cost equal to the number of elements used to make it.
Nonetheless, it is known [21] that even if the elements are weighted, for an
array of size $k$, one can solve both LIS and DTM in time $O(k\log k)$. ∎

###  6.4 $1+\epsilon$ Approximation for DTM with Update Time $O(\log^{2}n)$

The last step is to obtain a $1+\epsilon$ approximate solution using the above
techniques. In parallel, we always run the algorithm of Section 6.1 to
maintain a 2-approximate solution. In order to obtain a $1+\epsilon$
approximation algorithm, we use the framework of Section 3. To design our
block-based algorithm we start with an array of length $n$. We set the
preprocessing time to $O(k\log n)$ where $k$ is the size of the 2-approximate
solution (this we know by the parallel algorithm that we run). In the
preprocessing phase, we find an exact solution (say $k^{\prime}\geq k/2$) in
time $O(k\log^{2}n)$777The additional $O(\log n)$ factor is due to the data
structure used for random access to the elements of the array. for the array
and report it as the value of distance to monotonicity. We set $g(a)=\epsilon
k/2$ and for the next $\epsilon k/2$ steps, we report $d+i$ for the $i$’th
operation where $d$ is the solution for the initial array. This is clearly an
upper bound on the size of the solution as well as a $1+\epsilon$
approximation of it. Thus, the worst-case update time is $O(1)$.

By Lemma 3, our block-based algorithm can be turned into a dynamic algorithm
with worst-case update time $O(\log^{2}n)$.

######  Theorem 14.

For any $\epsilon>0$, there exists a dynamic algorithm for distance to
monotonicity with approximation factor $1+\epsilon$ and worst-case update time
$O(\log^{2}n)$.

###### Proof.

For an array $a$, our block-based algorithm has preprocessing time
$f(a)=O(k\log^{2}n)$ where $k=\mathsf{DTM}(a)$. Also, $g(a)=\epsilon k/2$ and
$h(a)=O(1)$. Thus, by Lemma 2, the worst-case update time of the equivalent
dynamic algorithm is $O(\log^{2}n)$. Notice that since after $g(a)$ steps the
size of the $\mathsf{DTM(a)}$ changes by a small factor, all functions $f,g,$
and $h$ remain asymptotically the same which implies relativity. ∎

## References

  * [1] N. Ailon, B. Chazelle, S. Comandur, and D. Liu.  Estimating the distance to a monotone function.  In RANDOM 2004.
  * [2] A. Andoni and H. L. Nguyen.  Near-optimal sublinear time algorithms for ulam distance.  In SODA 2010.
  * [3] S. Assadi, K. Onak, B. Schieber, and S. Solomon.  Fully dynamic maximal independent set with sublinear in n update time.  In SODA 2019.
  * [4] S. Assadi, K. Onak, B. Schieber, and S. Solomon.  Fully dynamic maximal independent set with sublinear update time.  In STOC 2018.
  * [5] S. Behnezhad, M. Derakhshan, M. Hajiaghayi, C. Stein, and M. Sudan.  Fully dynamic maximal independent set with polylogarithmic update time.  In FOCS 2019.
  * [6] M. Boroujeni and S. Seddighin.  Improved MPC algorithms for edit distance and ulam distance.  In SPAA 2019.
  * [7] A. Chen, T. Chu, and N. Pinsker.  The dynamic longest increasing subsequence problem.  arXiv preprint arXiv:1309.7724, 2013.
  * [8] G. Cormode, M. Mitzenmacher, and J. Thaler.  Streaming graph computations with a helpful advisor.  In ESA 2010.
  * [9] S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani.  Algorithms.  McGraw-Hill Higher Education, 2008.
  * [10] Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky.  Improved testing algorithms for monotonicity.  In RANDOM-APPROX 1999.
  * [11] F. Ergün, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan.  Spot-checkers.  In STOC 1998.
  * [12] E. Fischer.  The art of uninformed decisions.  Bulletin of the EATCS, 75:97, 2001.
  * [13] M. L. Fredman.  On computing the length of longest increasing subsequences.  Discrete Mathematics, 11(1):29–35, 1975.
  * [14] A. Gál and P. Gopalan.  Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence.  In FOCS 2007.
  * [15] P. Gawrychowski and W. Janczewski.  Fully dynamic approximation of lis in polylogarithmic time, 2020.
  * [16] P. Gawrychowski, A. Karczmarz, T. Kociumaka, J. Łacki, and P. Sankowski.  Optimal dynamic strings.  In SODA 2018.
  * [17] P. Gopalan, T. S. Jayram, R. Krauthgamer, and R. Kumar.  Estimating the sortedness of a data stream.  In SODA 2007.
  * [18] A. Grønlund and S. Pettie.  Threesomes, degenerates, and love triangles.  In FOCS, 2014.
  * [19] M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In STOC 2015.
  * [20] S. Im, B. Moseley, and X. Sun.  Efficient massively parallel methods for dynamic programming.  In STOC 2017.
  * [21] G. Jacobson and K.-P. Vo.  Heaviest increasing/common subsequence problems.  In Annual Symposium on Combinatorial Pattern Matching, pages 52–66. Springer, 1992.
  * [22] T. Kociumaka and S. Seddighin.  Improved dynamic algorithms for longest increasing subsequence, 2020.
  * [23] J. Lacki, J. Ocwieja, M. Pilipczuk, P. Sankowski, and A. Zych.  The power of dynamic distance oracles: Efficient dynamic algorithms for the steiner tree.  In STOC 2015.
  * [24] M. Mitzenmacher and S. Seddighin.  Dynamic algorithms for LIS and distance to monotonicity.  In STOC, 2020.
  * [25] M. Mitzenmacher and S. Seddighin.  Erd$\backslash$”$\\{$o$\\}$ s-szekeres partitioning problem.  arXiv preprint arXiv:2011.10870, 2020.
  * [26] M. Mitzenmacher and S. Seddighin.  Improved sublinear time algorithms for longest increasing subsequence.  In SODA, 2021.
  * [27] D. Nanongkai and T. Saranurak.  Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o(n${}^{\mbox{1/2 - {$\epsilon$}}}$)-time.  In STOC 2017.
  * [28] D. Nanongkai, T. Saranurak, and C. Wulff-Nilsen.  Dynamic minimum spanning forest with subpolynomial worst-case update time.  In FOCS 2017.
  * [29] T. Naumovitz, M. E. Saks, and C. Seshadhri.  Accurate and nearly optimal sublinear approximations to ulam distance.  In SODA 2017.
  * [30] S. Pettie.  On the shortest path and minimum spanning tree problems.  PhD thesis, 2003.
  * [31] P. Ramanan.  Tight $\omega$ (n lg n) lower bound for finding a longest increasing subsequence.  International journal of computer mathematics, 65(3-4):161–164, 1997.
  * [32] A. Runbinstein, S. Seddighin, Z. Song, and X. Sun.  Approximation algorithms for LCS and LIS with truly improved running times.  In FOCS, 2019.
  * [33] M. Saks and C. Seshadhri.  Estimating the longest increasing sequence in polylogarithmic time.  In FOCS, 2010.
  * [34] R. B. Yehuda and S. Fogel.  Partitioning a sequence into few monotone subsequences.  Acta Informatica, 35(5):421–440, 1998.

##  Appendix A Streaming Algorithm for LIS

We outlined an improved streaming algorithm for LIS in Section 2. Here we give
a proof for its correctness and a bound on its memory. In this setting, we
assume that the input is available to us in any desired order. We call this
setting, streaming with advisory help. Previous work solves the problem with
memory $O(\sqrt{n})$ within a factor $1+\epsilon$ in a single round [17].

######  Observation 3.

For any $0<\kappa<1$, there exists a streaming algorithm that uses advisory
help and approximates the LIS of an array of length $n$ with memory
$\tilde{O}(n^{2/5+\kappa})$ within a factor $O(1/\kappa)$ in three rounds.
This algorithm is randomized and gives an approximate solution with
probability at least $1-1/n$.

###### Proof.

Let $m=n^{1/5}$ be the size of the grid. We use an $(O(m^{\kappa}\log
m),O(1/\kappa))$ approximate solution of grid packing to cover the grid cells
with segments. Similar to what we did before, we think of each element $i$ of
the array as a point $(i,a_{i})$ of the 2D plane. As mentioned earlier, in the
first round, we sample $m-1$ elements from the array. We use these elements to
draw the horizontal lines of the grid. It follows from standard Chernoff bound
that since the elements are chosen uniformly at random, the number of elements
in every row of the grid is bounded by $10n/m\log n$ with probability at least
$1-1/n$. Also, we draw the vertical lines evenly so that they divide the
elements into chunks of size $n/m$.

In the next two rounds, we ask for the elements of the array in the row-order
and column-order. More precisely, in the second round, we first ask for the
elements falling in the first row of the grid (in the column order). Next, we
ask for the elements of the second row and so on. For each row, we approximate
the value of the LIS for each segment. Since the total number of elements in
every row is bounded by $10n/m\log n$, we only need memory
$\tilde{O}(\sqrt{n/m\log n})=\tilde{O}(n^{2/5})$ to approximate the value of
LIS for each segment. However, we need this much memory for multiple segments.
This adds an overhead of $\tilde{O}(m^{\kappa})$ to the memory since each grid
cell may be covered by at most $\tilde{O}(m^{\kappa})$ segments. Similarly, in
the third round, we ask for the elements in the column-order.

Finally, we use a DP to find a subset of non-conflicting segments with the
largest total sum of LIS. This can be done with memory
$\tilde{O}(m^{2+\kappa})=\tilde{O}(n^{2/5+\kappa})$ as the number of segments
is bounded by $\tilde{O}(m^{2+\kappa})$.

The correctness of the algorithm is similar to the one given for dynamic LIS.
We fix an arbitrary LIS of the array and assume that the adversary puts the
contribution of each cell of the grid to the fixed LIS. The LIS of each
segment is a clear upper bound on the score of that segment on the grid,
however, if we use those values instead of their scores, we still obtain a
valid solution. Finally, since our solution for the grid packing problem is
$(O(m^{\kappa}\log m),O(1/\kappa))$ approximate, then the score we obtain
using non-conflicting segments is at least an $\Omega(\kappa)$ fraction of the
score of the grid which is equal to the size of the LIS. ∎

##  Appendix B Improved Algorithm for $\mathsf{LIS}^{+}$

We provide the intuition behind the algorithm and then the formal proof. For
simplicity, we assume here that we have random access to all elements of the
array in time $O(1)$. Our first goal is to design a block-based algorithm for
an array $a$ of length $n$. We set $f(n)=O(n\log n)$ and in the preprocessing
phase we compute the LIS of $a$. Let this value be $x$. Since we only add
elements in the $\mathsf{LIS}^{+}$ problem, from here on, $x$ is a lower bound
for the solution value. For the next $g(n)=\sqrt{n}$ operations, every new
element is added to a separate set, and after each operation, the LIS of the
separate set is computed in time $O(\sqrt{n}\log n)$. At an arbitrary step,
let this value be $y$. The key observation is that the overall LIS of the
array is in range $[\max\\{x,y\\},x+y]\leq 2\max\\{x,y\\}$. We therefore have
a 2-approximate solution by just reporting $\max\\{x,y\\}$. This block-based
algorithm for $\mathsf{LIS}^{+}$ with $f(n)=O(n\log n)$, $g(n)=\sqrt{n}$, and
$h(n)=O(\sqrt{n}\log n)$ yields a dynamic algorithm with worst-case update
time $\tilde{O}(\sqrt{n})$.

We recurse to improve the runtime down to $O(n^{\epsilon})$ for any
$\epsilon>0$. Instead of using the naive algorithm for the $g(n)$ operations
after the initialization, we can use the more advanced algorithm explained
above (its update time is $\tilde{\Omega}(\sqrt{n})$ better than computing the
LIS from the scratch every time). Similar to what we did in 5, in each level
of recursion, we use the previous algorithm for the operations after
initialization. The advantage of this approach in this setting over Section 5
is that the approximation factor of the algorithm depends linearly on
$1/\epsilon$ (and not exponentially). To see this, assume that at some point,
$x$ is the solution for the initial array and $y$ is an $\alpha$-approximation
for the solution of the second set of operations. The optimal solution is
upper bounded by $x+\alpha y$ and lower bounded by $\max\\{x,y\\}$. Therefore,
by reporting $\max\\{x,y\\}$ we can be sure that our approximation factor is
bounded by $\alpha+1$. In other words, if we recurse on this algorithm
$\alpha$ times, then the approximation factor is bounded by $\alpha+1$. This
results in an algorithm with worst-case update time $\tilde{O}(n^{\epsilon})$
and approximation factor $O(1/\epsilon)$.

######  Observation 4.

For any constant $\epsilon>0$, there exists an algorithm for dynamic
$\mathsf{LIS}^{+}$ whose worst-case update time is $\tilde{O}(n^{\epsilon})$
and whose approximation factor is $O(1/\epsilon)$.

If one could show the statement of Observation 4 for any (possibly sub-
constant) $\epsilon>0$, then by setting $\epsilon=1/\log n$, we could obtain a
dynamic algorithm for $\mathsf{LIS}^{+}$ with polylogarithmic update time and
logarithmic approximation factor. However, since there is a constant factor
overhead in every recursion, Observation 4 only works when $\epsilon$ is
constant. This overhead is incurred in the reduction from dynamic algorithms
to block-based algorithms. In the following, we provide a variation of the
same algorithm that does not use this reduction and achieves polylogarithmic
update with and logarithmic approximation.

$1$$1$$2$$1$$2$$3$$1$$2$$3$$4$$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$$6$$1$$2$$3$$4$$5$$6$$7$$1$$2$$3$$4$$8$$5$$6$$7$$1$$2$$3$$4$$5$$6$$7$$8$$9$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1:$$2:$$3:$$4:$$5:$$6:$$7:$$8:$$9:$$10:$
Figure 17: The buckets are shown for the first 10 operations. Buckets that are
disconnected and are held together with dashed rectangles are not finalized
yet. Connected pieces show finalized buckets.

######  Theorem 15.

There exists an algorithm for dynamic $\mathsf{LIS}^{+}$ whose worst-case
update time is $O(\log^{3}n)$ and whose approximation factor is $O(\log n)$.

###### Proof.

In our algorithm, we put the elements in buckets and for every bucket, we
compute the value of the LIS. As more buckets are made, we combine them to
construct larger buckets. The sizes of the buckets are always powers of 2.

In the beginning, the array is empty and there are no buckets. When the first
element is inserted, we construct the first bucket that contains only that
element. After the construction of each bucket, we compute the LIS of that
bucket over the next steps. More precisely, when a bucket of size $k$ is
constructed, we divide the task of computing the LIS of that bucket into $k$
pieces and execute these pieces in the next $k$ operations. Thus, when a
bucket of size $1$ is constructed, its LIS is computed immediately. We say a
bucket is finalized, when our algorithm has already computed its LIS. In our
algorithm, we only merge finalized buckets to make larger ones and thus, we
maintain the property that at each point in time, each element appears in
exactly one finalized bucket.

Every time a new element is inserted, we make a bucket containing that element
alone. However, when there are two finalized buckets of the same size (say
$k$), we merge them to obtain a bucket of size $2k$. After this, it takes
$2k-1$ more steps to finalize the new bucket but once the new bucket is
finalized, we remove the two smaller buckets. This way, each element appears
in exactly one finalized bucket at a time throughout the process.

At any point in time, we approximate the LIS of the array by the maximum
solution for any of the finalized buckets. We prove that with this
construction, there are at most $O(\log n)$ finalized buckets at every point
in time and moreover, the number of buckets that are not finalized is also
bounded by $O(\log n)$.

This immediately implies that the approximation factor of our algorithm is
bounded by $O(\log n)$. The reason is that each element is always included in
exactly one finalized bucket at a time and therefore the total sum of LIS’s
for all finalized buckets is an upper bound on the size of the solution.
Moreover, the maximum solution size for each bucket is a lower bound on the
LIS of the entire array. Since the number of finalized buckets is bounded by
$O(\log n)$ this implies that the approximation factor of our algorithm is
bounded by $O(\log n)$.

We also bound the runtime by $O(\log^{3}n)$. In our algorithm, at every point
in time, there are $O(\log n)$ different buckets that are not finalized yet.
The total runtime needed to compute the LIS of a bucket of size $k$ is
$O(k\log k)$ which is divided over $k$ steps. Thus, each bucket which is not
finalized yet requires time at most $O(\log n)$ for each step. Thus the
overall runtime is $O(\log^{2}n)$ for each step. One thing to keep in mind is
that we use a balanced tree data structure to access the elements of the array
which adds an overhead of $O(\log n)$. Therefore, the worst-case update time
is $O(\log^{3}n)$.

It follows from the construction of the buckets that at each step, there is at
most one bucket of each size which is not finalized. The reason is that after
a bucket of size $k$ is made, it takes $k$ more steps to make another bucket
of the same size. However, before the new bucket is made, the first one will
be finalized. Since the sizes of the buckets are powers of $2$, this implies
that there are most $\lfloor\log n\rfloor$ such buckets. Moreover, this also
shows that the number of finalized buckets of each size is bounded by $3$,
otherwise this makes two buckets of larger size that are not finalized yet. ∎

##  Appendix C Sequential Algorithm for DTM

We present a simple comparison-based algorithm for DTM with approximation
factor $2$ that runs in time $O(n)$. Using Lemma 12, the approximation factor
improves to $1+\epsilon$ in the following way: If the solution size is bounded
by $\sqrt{n}$, then Lemma 12 gives an exact solution in time
$\tilde{O}(\sqrt{n})$. Otherwise, one can find a $1+\epsilon$ approximate
solution in time $\tilde{O}(\sqrt{n})$ using the solution of [29]. Thus, the
main bottleneck of the runtime is for the computation of an approximate
solution, which we show can be done in time $O(n)$.

By Observation 1, a 2-approximate solution can be obtained by computing a
maximal set of inversion pairs. Our algorithm finds such a set in linear time.

We begin by a empty stack. We iterate over the elements of the array and each
time we compare the new element to the element at the top of the stack (if
any). If this pair makes an inversion, we put this pair in a set $S$ and
remove the last element of the stack. Otherwise, we put the new element on top
of the stack and continue on. Obviously, the runtime is $O(n)$, since each
element $a_{i}$ is processed in time $O(1)$. The correctness of the algorithm
follows from the fact that the numbers of the stack are always increasing and
therefore there is no inversion between them. Thus, set $S$ is a maximal set
of inversion pairs.

######  Observation 5.

For any constant $\epsilon>0$, DTM can be approximated within a factor
$1+\epsilon$ in time $O(n)$.

We remark that in the above observation, factors that depend on $1/\epsilon$
are hidden in the $O$ notation.

##  Appendix D The Algorithm of Chen et al. [7]

For formal proofs, we refer the reader to [7]. Chen et al. [7] propose the
following algorithm to maintain a solution for dynamic LIS.

For each element $i$ of the array, define $l(i)$ to be the size of the longest
increasing subsequence ending at element $a_{i}$ of the array. Chen et al. [7]
refer to this quantity as the level of element $i$. Notice that $l(i)$ can be
computed in time $\tilde{O}(n)$ for all elements of the array using the
patience sorting algorithm.

Define $L_{k}$ to be the set of elements whose levels are equal to $k$. The
algorithm of Chen et al. [7] maintains a balanced binary tree for each $L_{k}$
that contains the corresponding elements. One key observation is that for each
$k$, all the elements of $L_{k}$ are decreasing, otherwise their levels would
not be the same.

When a new element is added to the array, $L_{k}$’s may change. More
precisely, after an element addition, the levels of some elements may change
(but only by 1). Similarly, element removal may change the levels of the
elements of the array but again the change is bounded by $1$. Chen et al. [7],
show that after an insertion, for each $L_{k}$, the levels of only one
interval of the elements may increase. In other words, for each $L_{k}$, there
are two numbers $\alpha$ and $\beta$ such that all the elements whose values
are within $[\alpha,\beta]$ increase their levels and the rest remain in
$L_{k}$.

Thus, they use a special balanced tree structure that allows for interval
deletion and interval addition in logarithmic time. Therefore, all that
remains is to detect which interval of each $L_{k}$ changes after each
operation. They show that this can be computed in time $O(\log n)$ for all
$L_{k}$’s via binary search. Since the number of different levels is equal to
the size of the LIS, their update time depends on the size of the solution.

$L_{1}\ =\ \langle 1\rangle$$L_{2}\ =\ \langle 5,2\rangle$$L_{3}\ =\ \langle
4\rangle$$\langle 1,\ 5,\ 2,\
\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}3\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\
,\ 4,\ 6,\ 7,\ 9,\ 10,\ 8\rangle$$\langle 1,\ 5,\ 2\ ,\ 4,\ 6,\ 7,\ 9,\ 10,\
8\rangle$$L_{4}\ =\ \langle 6\rangle$$L_{5}\ =\ \langle 7\rangle$$L_{6}\ =\
\langle 9,8\rangle$$L_{7}\ =\ \langle 10\rangle$$3$ Figure 18: This examle
shows how adding element $3$ to the array changes the levels of the elements.
Upward arrows show that the level of the corresponding element increases after
we add $3$ to the array.

When $n$ elements are given, their runtime for constructing the data structure
is $\tilde{O}(n)$ since patience sorting gives us all the levels in time
$\tilde{O}(n)$ and the balanced trees can be constructed in time
$\tilde{O}(n)$ for all $L_{k}$.