Longest Increasing Subsequence under Persistent Comparison Errors

We study the problem of computing a longest increasing subsequence in a sequence $S$ of $n$ 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 $ p $, 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 $O(\log n)$-approximation in time $O(n\log n)$, with high probability. This approximation relies on the fact that that we can approximately sort $n$ elements in $O(n\log n)$ time such that the maximum dislocation of an element is at most $O(\log n)$. 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 $\Omega(\log n)$-approximation with high probability, and (ii) any $O(\log n)$-approximation algorithm for longest increasing subsequence requires $\Omega(n \log n)$ comparisons, even in the absence of errors.


Introduction
When dealing with complex systems and large volumes of information, it is often the case that at least part of the involved data will be inconsistent. These inconsistencies can be intrinsic, i.e., they might shed from the fact that the data is obtained from an inherently noisy source (this is typically the case in human-produced data), or they might be the result of corruptions caused by random errors (think, for instance, of random memory faults or communication errors). It is therefore important to understand how the classical techniques used to solve basic algorithmic problems can cope with such errors.
In this paper, we consider the problem of computing a longest increasing subsequence LIS(S) in a given sequence S of distinct elements -a fundamental task that appears naturally in many areas, such as in probability theory and combinatorics [2,4], scheduling [3,18], and computational biology [9,20]-in presence of random persistent comparison errors.
In this model, every comparison between two elements is wrong with some small fixed probability p, and correct with probability 1 − p. The comparison results are independent over all pairs of elements, and comparisons cannot be repeated. Note that this is equivalent to say that repeating the same comparison multiple times yields each time the same result. Hence, comparison results are persistent: always wrong or always correct. Furthermore, we assume that we cannot inspect the values of the elements, but only use such element comparisons. Because of these comparison errors, it is impossible to compute LIS(S) correctly, instead, we seek to return a sequence that (i) is indeed increasing and that (ii) has some guaranteed minimum length depending on the length of the longest increasing sequence l := |LIS(S)|. In particular, we are interested in algorithms that return an increasing sequence of length at least 1 r · l, where r is the approximation factor. This error model has been first employed by Braverman and Mossel [6], who studied the problem of sorting. Other work on sorting followed (see [12,13,16]) and the model has been studied also for finding the minimum, searching, and linear programming in two dimensions [16]. In this paper, we will present an algorithm that returns an O(log n)-approximation on the longest increasing subsequence in O(n log n) time, with high probability. Moreover, we will prove that this approximation factor is the best possible as Ω(log n) is also a lower bound, regardless of the running time, and that any (log n)-approximation algorithm requires Ω(n log n) comparisons, even in the absence of comparison errors.

Related Work
There are several algorithms to compute a longest increasing subsequence of a sequence S, if no comparison errors happen. Typically, they are based on a common underlying algorithmic idea: They process the elements one by one and maintain for each length found so far the increasing subsequence of this length that ends with the smallest possible element seen so far. We shall call this algorithmic idea the Core-Algorithm to compute a longest increasing subsequence. The running time of the Core-Algorithm is O(n log n) in the decision-tree model (see for instance [5,7,10]). This time complexity is tight, as shown in [10]. In the RAM model, where one can also inspect the values, the algorithm can be implemented to run in O(n log log n) time [8,19]. All the results can be parameterized to O(n log l) or O(n log log l), respectively, where l is the length of the longest increasing subsequence.
The longest increasing subsequence of S is also the longest common subsequence between S and the sorted sequence of the elements in S. This implies an O(n 2 ) time (or O(n 2 / log n) 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 [10,17].
The model with random persistent comparison errors has been extensively studied for finding the smallest element, for searching, and for sorting (see for instance [6,12,13,16]). A common way to measure the quality of an output sequence in terms of sortedness, is to consider the dislocation of the elements. The dislocation of an element is the absolute difference between its position in the output sequence and its position in the correctly sorted sequence (its rank). Typically, one considers the maximum dislocation of any element in the output sequence and the total dislocation (the sum of the dislocations of all elements). It has been shown for instance in [14], that there is an algorithm with running time O(n log n) which achieves simultaneously maximum dislocation O(log n) and total dislocation O(n) with high probability, and that this is indeed the best one can hope for (i.e., there exist matching lower bounds that show that no possibly randomized algorithm can sort such that, with high probability, the maximum dislocation is o(log n) or the total dislocation is o(n)). A maximum dislocation of O(log n) implies the following: on the positive side, it is possible to derive the correct relative order of two elements whose ranks differ by at least Ω(log n); on the negative side, this is not possible for two elements whose ranks differ by less than O(log n). The results on the maximum dislocation of sorting are of interest for the problem of finding the longest increasing subsequence, because an increasing subsequence is also a sorted subsequence.

Our Contribution
We prove asymptotically tight upper and lower bounds on both the approximation factor and the running time for longest increasing subsequence under persistent comparison errors. For the upper bounds, we define an Approximation-Algorithm that computes an O(log n)-approximation to the longest increasing subsequence of S. In fact, it even finds the longest possible increasing subsequence under the implication that we cannot sort better than obtaining an order with maximum dislocation O(log n). Formally, we prove the following result: This result on the upper bound can be generalized to other error models. In fact, if we are given or able to obtain an approximately sorted sequence with maximum dislocation d, then our Approximation-Algorithm will return a 2d-approximation to the longest increasing subsequence. We discuss this point in the Conclusion (Section 6).
To prove our lower bound on the approximation factor of any algorithm solving LIS(S) under persistent comparison errors with high probability, we will identify a small collection of sequences that contain a longest increasing sequence of size Θ(log n) and that are likely to look the same in our error model. Then, we show for any algorithm that if it succeeds on one sequence of this collection by returning a constant number of elements of this increasing sequence it must fail on another sequence. In particular, we will prove the following theorem: Theorem 2 (Lower Bound -Approximation Factor). There exists a collection of sequences S (permutations of length n) and a probability distribution on S, such that no algorithm can return an O(log n)-approximation (for s suitable hidden constant that depends on p) of the longest increasing subsequence with probability 1 − 1 n .
We prove a lower bound of Ω(n log n) on the number of comparisons (which is a lower bound on the running time) needed to compute an O(log n)-approximation by considering the easier case in which all comparisons are correct, and by adapting the techniques used in [10] for proving a similar lower bound for exact (i.e., 1-approximate) algorithms: Theorem 3 (Lower Bound -Running Time). Any (log n)-approximation algorithm for longest increasing subsequence requires Ω(n log n) comparisons, even if no errors occur.

Preliminaries
Since we assume that all elements in the input sequence S = s 1 , s 2 , . . . , s n are distinct, we can also assume, for easier analysis and readability, that S is a permutation of the numbers (elements) {1, . . . , n}. By our error model, the elements in S posses a true linear order , i.e., S sort := 1, . . . , n , however, this order can only be observed through erroneous comparisons.
For two distinct elements x and y, we will write x < y to denote that x is smaller than y according to the true linear order (resp. x > y to denote that x is larger than y according to the true linear order), and we will write x ≺ y (resp. x ≻ y) to mean that x is observed to be smaller (resp. larger) than y in the comparison result. For a given sequence S and an element x ∈ S, we define rank(x, S) = 1 + |{y ∈ S : y < x}| to be the true rank of element x in S (note that ranks start from 1), and we define pos(x, S) ∈ [1, |S|] to be the position of x in S (positions also start from 1). The dislocation of x in S is then disl(x, S) = |pos(x, S) − rank(x, S)|, and the maximum dislocation of S is disl(S) = max x∈S disl(x, S). For a given sequence S, we let C ∈ {≺, ≻} ( n 2 ) denote the comparison outcomes that we can observe.
Finally, for z ∈ R, we write log z for the binary logarithm of z.
We continue the preliminaries with some results on sorting that we will use to prove our upper bound on the approximation factor.
Theorem 4 (Theorem 3 in [14]). There is an algorithm that approximately sorts, in O(n log n) worst-case time, n elements subject to random persistent comparison errors so that the maximum dislocation of the resulting sequence is O(log n), with probability 1 − 1 n .
Proof. Since the maximum dislocation in S apx is at most d, pos(apx i , S sort ) ∈ {i−d, . . . , i+ d} and pos(apx i+2d , S sort ) ∈ {i + d, . . . , i + 3d}. These intervals intersect in at most one position, and the claim follows since no two elements can appear in the same position.

Upper Bound and Approximation-Algorithm
We will modify the so-called Core-Algorithm (as named in Section 1.1, Related work) that computes a longest increasing subsequence in the absence of comparison errors, such that it computes an O(log n)-approximation with high probability in our error model. Before we do so, we first show that it is possible to identify a 2d-approximation by looking at S and a sequence S apx with maximum dislocation d. Since we can sort such that the maximum dislocation is O(log n) (see Theorem 4), this implies an O(log n)-approximation on LIS(S).

Upper Bound
The proof of the upper bound is based on the following fact and observation: • Without any comparison errors, the problem of finding LIS(S) is equivalent to the problem of finding a longest common subsequence between S and S sort , where S sort is the correctly sorted order of the elements in S.
• This leads to the following observation. Let S apx be the sequence obtained from approximately sorting S with comparison errors and consider now S apx as the total order over all elements, i.e., for each pair of elements, their comparison result is redefined as their relative order in S apx . Furthermore, let A be any algorithm that solves LIS(S) in the absence of errors. If A uses the redefined comparison results, it computes the longest common subsequence LCS(S, S apx ) between S and S apx .
The immediate idea of computing LCS(S, S apx ) comprises some difficulties, since this subsequence is not necessarily increasing and, on top of that, |LCS(S, S apx )| might be smaller than |LIS(S)|. However, we can still get a first approximation. Assume that S apx has maximum dislocation at most d. Lemma 1 implies that we obtain an increasing subsequence when taking every 2d-th element of LCS(S, S apx ). And the maximum dislocation implies that the elements in the subset containing every 2d-th element of LIS(S) appear in the same relative order in S apx , thus |LCS(S, S apx )| ≥ 1 2d |LIS(S)| . When put together, we get a 4d 2 -approximation.
This approximation factor can be improved, and it turns out that considering common subsequences whose elements lie (at least) 2d positions apart in S apx is actually a good start: By Lemma 1, a common subsequence between S and S apx is increasing if for every pair of adjacent elements in this subsequence their positions in S apx differ by at least 2d. Therefore, we say that a sequence Notice that any (increasing) subsequence of S that is 2d-distant in S apx is automatically also a common (increasing) subsequence of S and S apx . This observation suggests the following easy recipe to obtain a 2d-approximation on longest increasing subsequence: • First, partition the elements into 2d subsets, such that every 2d-th element in S apx gets into the same subset, and obtain 2d input subsequences based on this partition.
• Then, on every input subsequence, run any algorithm that computes a longest increasing subsequence if no comparison errors happen, and return the longest result.
By pigeon hole principle and since every input subsequence is now 2d-distant in S apx , the longest result must be a 2d-approximation on |LIS(S)|. This recipe however is not optimal in the sense that in many cases, we could do better and find a longer subsequence in S that is still 2d-distant in S apx . In fact, we lose up to a factor 2d in the case where LIS(S) is already 2d-distant in S apx , but these elements are equally distributed among all input subsequences. For this reason, we will define an approximation algorithm that finds the longest increasing subsequence in S that is 2d-distant in S apx . We conclude this section with the obvious lemma.
Lemma 2. The longest subsequence S * of S that is 2d-distant in S apx has length at least

Approximation-Algorithm
Consider the Core-Algorithm described in Algorithm 1 that computes the longest increasing subsequence of the input sequence S in the error-free case. The algorithm processes the input elements one by one, maintaining the longest increasing subsequence found so far. In particular, it maintains a parameter k and an array L, such that k is the length of the longest increasing subsequence found so far and L contains an entry for each length 1 to k, such that L[i] stores the smallest element processed so far that can be at the end of an increasing subsequence of length i.
• The first element is placed to L[1] and k is set to 1.
• Each subsequent element x is placed to L[j + 1], such that j is the largest position where y = L[j] is smaller than x. • If x is placed to L[k + 1], then k is updated to k + 1.
• Whenever a new element x is placed, put a pointer prec from x to the element in y = L[j], that, by construction, has a lower value than x.
• In the end, follow these pointers from the top element of the last pile to recover the longest increasing subsequence (in reverse order).
An entry L[j] basically represents the increasing sequence of length j that ends with the smallest possible element processed so far. When an element x is inserted into some position L[j +1] this means that it is appended to the sequence represented by L[j]. Hence, x either increases the longest increasing sequence so far (case j = k) or the sequence L[j+1] gets replaced by this new sequence (case x < L[j + 1]).
Our Approximation-Algorithm, as described in Algorithm 2, is obtained by modifying the Core-Algorithm such that it works in our error model.
• We first approximately sort (using the algorithm from [14], see also Theorem 4 in the current paper) the elements of S to obtain S apx , and we redefine the comparison outcomes based on this total order, i.e., the result of a comparison between two elements now corresponds to their relative order in S apx .
• To compute a suitable subsequence, we change the algorithm so that it remembers the longest 2d-distant in S apx subsequences instead of the longest increasing subsequences. This implies that an element x is only appended to an (intermediate) subsequence that ends with element y, if pos(y, S apx ) + 2d < pos(x, S apx ).
For easier analysis, we introduce some additional notation. We call one execution of the lines 4 to 11 of Algorithm 2 an iteration, and enumerate them such that element s i is considered in iteration i. We also say that line 3 corresponds to the first iteration. Furthermore, we denote by L t and k t the state and the value of L and k after the t-th iteration, respectively, and for any j ≤ k t , we call the subsequence L t  Proof. For any t and j ≤ k t , let S ′ = s ′ 1 , . . . , s ′ m be the implied sequence of L t [j]. Observe that to every element s ′ i ∈ S ′ , such that i > 1, the algorithm has assigned s ′ i−1 as its predecessor. Since the predecessor of any element can only have been processed in an earlier iteration, S ′ is a subsequence of S.
It follows by induction, that the condition on line 9 in Algorithm 2 ensures that S ′ is 2d-distant in S apx : It is trivial to see for t = 1, thus, assume that every implied sequence before the t-th iteration is 2d-distant in S apx . If s t is inserted into L[j] (nothing changes in the other case), the implied sequence of L t [j] is equal to s t appended to the implied sequence of L t−1 [j − 1] (if it exists). By hypothesis and the condition on line 9, L t [j] is still 2d-distant, and since the other implied sequences do not change, the claim also holds after iteration t.
That  . . , s ′ m be the sequence that our Approximation-Algorithm returns. Then, S ′ is a longest subsequence of S that is 2d-distant in S apx .
Proof. Lemma 3 implies that S ′ is a subsequence of S and 2d-distant in S apx . Let S * = s * 1 , . . . , s * m * be a longest subsequence of S that is 2d-distant in S apx . We now show that |S ′ | ≥ |S * |. In particular, we show by induction that after iteration t * i , pos(L t * i [i], S apx ) ≤ pos(s * i , S apx ). For the base case, consider iteration t * 1 , where s * 1 is processed. Either s * 1 gets inserted into some position j ≥ 1, i.e., L t * 1 [j] = s * 1 , or not. If it gets inserted, then by conditions in lines 6 or 8 in Algorithm 2, pos(L t * 1 [1], S apx ) ≤ pos(s * 1 , S apx ). If not, then it must hold that L t * 1 [1] = L t * 1 −1 [1] and thus pos(L t * 1 [1], S apx ) < pos(s * 1 , S apx ) . For the step case, consider iteration t * i+1 , where s * i+1 is processed, and observe that the value of k only increases during the algorithm, and for any t ′ < t and j ≤ k t ′ it holds that pos(L t ′ [j], S apx ) ≥ pos(L t [j], S apx ) . Therefore, and by induction hypothesis and the assumption that S * is 2d-distant in S apx , pos(L t * i+1 −1 [i], S apx )+ 2d ≤ pos(s * i+1 , S apx ) . And Lemma 3 implies, pos . Thus, if s * i+1 does not get inserted, it is because pos(L t * i+1 −1 [i + 1], S apx ) < pos(s * i+1 , S apx ), and if it gets inserted, it will be in some position j ≥ i + 1. In any case, the hypothesis also holds after the iteration iteration t * i+1 , which means that S ′ has indeed maximum length.

Proof of Theorem 1
We now prove the initially stated Theorem 1, which for convenience, we restate here: Theorem 1 (Upper Bounds). For any sequence S that contains n distinct elements, our Approximation-Algorithm computes an O(log n)-approximation of the longest increasing sequence of S, in O(n log n) time, with probability at least 1 − 1 n .
Proof. Let d ∈ O(log n) according to Theorem 4, such that with probability 1− 1 n , the maximum dislocation in S apx is at most d. If this is true, by Lemmata 1-4, our Approximation-Algorithm returns a subsequence S ′ of S that is increasing, and that has length at least ∈ Ω LIS(S) log n .

Lower Bound on the Approximation Factor
We continue this paper with a lower bound on the approximation factor, that implies that the upper bound we showed in Theorem 1 is tight up to constant factors. In particular, we prove Theorem 2, which we restate here: Theorem 2 (Lower Bound -Approximation Factor). There exists a collection of sequences S (permutations of length n) and a probability distribution on S, such that no algorithm can return an O(log n)-approximation (for some suitable hidden constant that depends on p) of the longest increasing subsequence with probability 1 − 1 n .
Our proof can be seen as a generalization of the lower bound on the maximum dislocation for sorting (see proof of Theorem 9 in [12]), where it is shown that two elements whose ranks differ by less than O(log n) are likely to be indistinguishable by any algorithm, and hence to appear in the wrong relative order. Intuitively, the argument there is as follows: consider the sorted sequence and the sequence obtained by swapping two elements, and assume that the comparison outcomes on these sequences look identically. It turns out that the probability of this happening is larger than 1 n , whenever the rank difference is smaller than O(log n), since only a small number of comparison outcomes must differ. This is not enough in our case, since an algorithm could simply ignore such two elements. For instance, consider an increasing sequence of c adjacent elements. If the first and the last element are swapped, the algorithm could simply return the subsequence without these two elements and be almost optimal. A first idea to fix this problem could be to consider the case, where one observes the whole increasing sequence to be reversed. However, to have this happen with probability larger than 1 n , c needs to be smaller than O( √ log n), thus implying a weaker lower bound.
Instead, we shall use a collection of similar sequences (more than two), such that if an algorithm succeeds on one of these sequences it must fail on another one.
Proof. We say that an algorithm succeeds if it returns a (c log n)-approximation for any constant c < 1 2 log 1−p p , otherwise we say it fails. We shall first define our collection S of similar sequences. Let η := ⌈ log n 2 log 1−p p ⌉. Let S * denote the sequence, in which the largest η elements appear first in increasing order and then the remaining elements appear in decreasing order, S * := n − η + 1, . . . , n − 1, n, n − η, . . . , 1 .
Now, let S := {S * , S (1) , S (2) , . . . , S (η−1) } (note that basically S * = S (η) ) and let P be the uniform distribution over S. We will show (proof by contradiction) that no algorithm succeeds on this pair (S, P) with probability at least 1 − 1 n . Assume towards a contradiction that algorithm A succeeds with high probability on a sequence S ′ chosen uniformly at random from S, i.e., This implies that since by hypothesis and assuming the case where the algorithm succeeds on all the other input sequences (i.e., best case for the algorithm, worst case for the proof), P η + η−1 η ≥ 1− 1 n resolves to (2). Let C ∈ {≺, ≻} ( n 2 ) , then A(S, C) means that algorithm A runs on sequence S and observes comparison outcomes C. Now, consider the set of all comparison outcomes that the algorithm can observe and let C := {C ∈ {≺, ≻} ( n 2 ) : A(S * , C) succeeds} denote the set of all possible comparison outcomes for which A succeeds on input S * . We define R(S) ∈ {≺, ≻} ( n 2 ) to be the random variable corresponding to the comparison outcomes as they would be observed by the algorithm when the input sequence is S. Then, the probability that A(S * ) succeeds is expressed by the total probabilities of the events that A observes comparison outcomes in C, Before we continue the proof, we shall first show the following lemma. Proof. Consider S * = s * 1 , . . . , s * n and C and let E(S * , C) be the set of wrong comparison results, i.e., the set of pairs (s * i , s * j ) with i < j such that either s * i < s * j and c (i−1)n+j = " ≻ " (i.e., s * i ≻ s * j ) or s * i > s * j and c (i−1)n+j = " ≺ ". Thus, . Now consider S = S (k) = s 1 , . . . , s n and observe that only the relative order of the pairs (s k , s j ) with k < j ≤ η, changed compared to S * . This implies that there can be at most η − k < η additional wrong comparison results, i.e., |E(S, C)| < |E(S * , C)| + η. Therefore, and since p 1−p ≤ 1, Continuation of the Proof of Theorem 2. Now notice that in order to succeed, A needs to return at least two of the first η elements in S * . Therefore, we can map every C ∈ C to a (not necessarily unique) sequence of S as follows: for each C ∈ C, let i C be the position of the first element that A(S * , C) returns and let S(C) := S (i C ) . (Note that i C < η as otherwise A does not return at least two elements of the first η elements in S * .) For each S ∈ S \ {S * },

Lower Bound on the Running Time
We complement this paper by showing that the running time of our Approximation-Algorithm is asymptotically optimal. In [10], it is shown that (in the error-free model) computing the longest increasing subsequence is at least as hard as sorting. We will use this proof to informally show Theorem 3 which we restate here (we postpone a formal proof to the full version of the paper): Theorem 3 (Lower Bound -Running Time). Any log n-approximation algorithm for longest increasing subsequence requires Ω(n log n) comparisons, even if no errors occur.
The proof techniques of the lower bound in [10] are as follows: Assume that we are in the error-free case. Consider the easier problem of deciding on a given sequence S of n distinct elements whether |LIS(S)| < k, and consider the comparison tree of an algorithm A with leaves that tell as an answer to this question either "yes" or "no". Without loss of generality, assume that no useless comparisons are made on a root to a leaf path (i.e., no comparison twice and no comparisons whose outcome is predictable by the outcomes of previous comparisons).
Every leaf ℓ can be associated with a partial order implied by a set of linear orderings on S that are consistent with the transitive closure of the comparisons performed on the path from the root to ℓ. If the answer in a leaf is "yes", this implies that there are no k elements of S that are pairwise incomparable in this partial order (i.e., the relative order of every pair is neither tested in any comparison on the path, nor implied by other comparisons), as otherwise, these elements could possibly form an increasing sequence of length k. Such a subset of elements is called antichain, while a chain is a subset of elements that are linearly ordered. An important property of chains and antichains used in the proof is, that in a "yes"-leaf, the elements can be partitioned into less than k chains, since in any partial order, the elements can be partitioned into m chains, where m is the size of the largest antichain. Furthermore, given such a partition into (less than) k chains, the elements can be sorted with n log k + O(n) comparisons (think for instance of natural merge sort).
In order to lower bound the number of comparisons needed to end in a "yes"-leaf, algorithm A can be extended to A * as follows: whenever A concludes to be in a "yes"leaf, A * continues to completely sort the elements of S (which requires no more than n log k + O(n) further comparisons). Let S(n, k) denote the number of linear orderings of the elements in S that end in a "yes"-leaf. Then, S(n, k) ≥ n!(1 − n k+1 /(k)!) , since there are n! different linear orderings and n k possible subsequences of size k each increasing with probability 1/k!. The comparison tree corresponding to A * has thus at least S(n, k) leaves, and therefore must perform at least log S(n, k) comparisons in its worst case. Therefore, A must perform at least log S(n, k) − n log k − O(n) comparisons in its worst case to end up in a "yes"-leaf, which is Ω(n log n) when choosing k = 3 · √ n.
We can use the above proof techniques to show that every algorithm, that computes a log n-approximation on longest increasing subsequence must perform at least Ω(n log n) comparisons. Let B be an log n-approximation algorithm for LIS(S) under our error model (i.e., we can always simulate our error model in the error-free case) and consider a relaxation of the problem of determining whether |LIS(S)| is smaller than k log n. In this relaxation we require the answer to be "yes" (resp. "no") if |LIS(S)| < k (resp. |LIS(S)| ≥ k log n), while we do not impose any restriction on the range k ≤ |LIS(S)| < k log n. It is clear that algorithm B can be used to solve this relaxed problem without increasing the number of needed comparisons. Therefore, the associated comparison tree must reach a leaf corresponding to answer "yes" for all linear orderings on the elements in S that contain no increasing subsequence of length k, while the largest antichain in any such an ordering is smaller than k log n. This implies that B * (still in the error-free case) needs at least n log(k log n) + O(n) further comparisons in the worst case to sort the elements in S, and B needs at least log S(n, k) − n log(k log n) − O(n) comparisons in the worst case to end in a "yes"-leaf, which is in Ω(n log n) if we set k = n 2/3 . Finally, we can conclude that our Approximation-Algorithm performs in asymptotically optimal time, since we can always simulate our error model in the error-free case.

Conclusion
Although a logarithmic approximation ratio might not seem very exciting at first glance, it turns out that this is the best one that can be obtained in the presence of persistent comparison errors. In this respect, it is interesting to see that there exist such a simple recipe to compute a logarithmic approximation. A recipe that can use as a black box any algorithm that computes a longest increasing sequence if no comparison errors happen: • First, obtain an approximately sorted sequence S apx of the elements such that the maximum dislocation is d and redefine the comparisons according to this order. Then, partition the elements into 2d subsets, such that every 2d-th element in S apx gets into the same partition, and obtain 2d input subsequences based on this partition. Finally, run the algorithm on every input subsequence and return the longest result.
As indicated earlier, our Approximation-Algorithm has the advantage, that it performs much better than O(log n)-approximate on many input sequences and is even optimal in the case where the longest increasing subsequence is already 2d-distant in S apx , whereas this is not necessarily true when using the simple recipe. Moreover, it is easy to observe that the Approximation-Algorithm is never worse than the recipe.
Finally, we would like to explain how the upper bound on the approximation factor can be generalized. Our Approximation-Algorithm actually succeeds whenever the approximately sorted sequence has maximum dislocation at most d. This implies that the result can be parametrized and also used in other models with comparison comparison errors.
• Whenever one can obtain a total order with maximum dislocation d, the Approximation-Algorithm is 2d-approximative.
Consider for instance the so-called threshold-model [1,11,15], where comparisons between numbers that differ by more than some threshold τ are always correct, while those between numbers that differ by less than τ can fail persistently (with some probability possibly depending on the difference or even adversarially). If the input sequence S is a permutation of the numbers {1 . . . , n}, running Quicksort in this error model yields a sequence with maximum dislocation 2τ (see [15]). Thus, our Approximation-Algorithm finds a 4τ -approximation of the longest increasing subsequence in S.