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.
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 .
@cite_5 @cite_8
2069893028 2009853785 1989633256 1559523984
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. We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers 1,2,...,n can be computed in time O(nloglogk) in the RAM model, improving the previous 30-year bound of O(nlogk). The algorithm also improves on the previous O(nloglogn) bound. The optimality of the new bound is an open question. Reducing the computation of a longest common subsequence (LCS) between two strings to an LIS computation leads to a simple O(rloglogk)-time algorithm for two sequences having r pairs of matching symbols and an LCS of length k. We study the length of the longest increasing and longest decreasing subsequences of random permutations drawn from the Mallows measure. Under this measure, the probability of a permutation ( S_n ) is proportional to (q^ Inv ( ) ) where (q ) is a real parameter and ( Inv ( ) ) is the number of inversions in ( ). The case (q=1 ) corresponds to uniformly random permutations. The Mallows measure was introduced by Mallows in connection with ranking problems in statistics. We determine the typical order of magnitude of the lengths of the longest increasing and decreasing subsequences, as well as large deviation bounds for them. We also provide a simple bound on the variance of these lengths, and prove a law of large numbers for the length of the longest increasing subsequence. Assuming without loss of generality that (q<1 ), our results apply when (q ) is a function of (n ) satisfying (n(1-q) ). The case that (n(1-q)=O(1) ) was considered previously by Mueller and Starr. In our parameter range, the typical length of the longest increasing subsequence is of order (n 1-q ), whereas the typical length of the longest decreasing subsequence has four possible behaviors according to the precise dependence of (n ) and (q ). We show also that in the graphical representation of a Mallows-distributed permutation, most points are found in a symmetric strip around the diagonal whose width is of order (1 (1-q) ). This suggests a connection between the longest increasing subsequence in the Mallows model and the model of last passage percolation in a strip. A natural problem in extremal combinatorics is to maximize the number of distinct subsequences for any length- @math string over a finite alphabet @math ; this value grows exponentially, but slower than @math . We use the probabilistic method to determine the maximizing string, which is a cyclically repeating string. The number of distinct subsequences is exactly enumerated by a generating function, from which we also derive asymptotic estimates. For the alphabet @math , @math has the maximum number of distinct subsequences, namely @math . We also consider the same problem with sub strings in lieu of sub sequences . Here, we show that an appropriately truncated de Bruijn word attains the maximum. For both problems, we compare the performance of random strings with that of the optimal ones.