We study the problem of computing a longest increasing subsequence in a sequence @math of @math distinct elements in the presence of persistent comparison errors. In this model, every comparison between two elements can return the wrong result with some fixed (small) probability @math , and comparisons cannot be repeated. Computing the longest increasing subsequence exactly is impossible in this model, therefore, the objective is to identify a subsequence that (i) is indeed increasing and (ii) has a length that approximates the length of the longest increasing subsequence. We present asymptotically tight upper and lower bounds on both the approximation factor and the running time. In particular, we present an algorithm that computes an @math -approximation in time @math , with high probability. This approximation relies on the fact that that we can approximately sort @math elements in @math time such that the maximum dislocation of an element is at most @math . For the lower bounds, we prove that (i) there is a set of sequences, such that on a sequence picked randomly from this set every algorithm must return an @math -approximation with high probability, and (ii) any @math -approximation algorithm for longest increasing subsequence requires @math comparisons, even in the absence of errors.
@cite_5: Let S = x"1, x"2, ... x"n be a sequence of n distinct elements from a linearly ordered set. We consider the problem of determining the length of the longest increasing subsequences of S. An algorithm which performs this task is described and is shown to perform n log n-n log log n + O(n) comparisons in its worst case. This worst case behavior is shown to be best possible.
@cite_8: The edit distance between two character strings can be defined as the minimum cost of a sequence of editing operations which transforms one string into the other. The operations we admit are deleting, inserting and replacing one symbol at a time, with possibly different costs for each of these operations. The problem of finding the longest common subsequence of two strings is a special case of the problem of computing edit distances. We describe an algorithm for computing the edit distance between two strings of length n and m, n ⪖ m, which requires O(n · max(1, mlog n)) steps whenever the costs of edit operations are integral multiples of a single positive real number and the alphabet for the strings is finite. These conditions are necessary for the algorithm to achieve the time bound.
The longest increasing subsequence of @math is also the between @math and the sorted sequence of the elements in @math . This implies an @math time (or @math time if optimized) algorithm to find the longest increasing subsequence when using the standard dynamic programming technique that is used to find longest common subsequences @cite_5 @cite_8 .