Question on an Algorithm for Longest Increasing Subsequence
Update:
I have thoroughly read through the paper myself and understand the problem better. So the algorithm fails if I make the above deletion (i.e. removing elements from a boundary layer). Layers $L_i = \{a_j | b_j = i\}$ are only for initialization, and for the duration of the algorithm, only the boundary layers are kept in tact to calculate one of the local data structure (which assumes the boundary layers are unchanged). This is a probabilistic algorithm and the paper show that we can get success rate to $1-n^{-10}$ after $20\log n$ repeats.