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_0: The vast quantities of log-based data appearing in data centers has generated an interest in sorting almost-sorted datasets. We revisit the problem of sorting and merging data in main memory, and show that a long-forgotten technique called Patience Sort can, with some key modifications, be made competitive with today's best comparison-based sorting techniques for both random and almost sorted data. Patience sort consists of two phases: the creation of sorted runs, and the merging of these runs. Through a combination of algorithmic and architectural innovations, we dramatically improve Patience sort for both random and almost-ordered data. Of particular interest is a new technique called ping-pong merge for merging sorted runs in main memory. Together, these innovations produce an extremely fast sorting technique that we call P3 Sort (for Ping-Pong Patience+ Sort), which is competitive with or better than the popular implementations of the fastest comparison-based sort techniques of today. For example, our implementation of P3 sort is around 20 faster than GNU Quicksort on random data, and 20 to 4x faster than Timsort for almost sorted data. Finally, we investigate replacement selection sort in the context of single-pass sorting of logs with bounded disorder, and leverage P3 sort to improve replacement selection. Experiments show that our proposal, P3 replacement selection, significantly improves performance, with speedups of 3x to 20x over classical replacement selection.
@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_15: In this paper we present three algorithms that solve three combinatorial optimization problems related to each other. One of them is the patience sorting game, invented as a practical method of sorting real decks of cards. The second problem is computing the longest monotone increasing subsequence of the given sequence of n positive integers in the range 1,…,n. The third problem is to enumerate all the longest monotone increasing subsequences of the given permutation.
@cite_10: 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.
@cite_11: Let A= and B= be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence , where i"1
There are several algorithms to compute a longest increasing subsequence of a sequence @math , 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 to compute a longest increasing subsequence. The running time of the Core-Algorithm is @math in the decision-tree model (see for instance @cite_15 @cite_0 @cite_5 ). This time complexity is tight, as shown in @cite_5 . In the RAM model, where one can also inspect the values, the algorithm can be implemented to run in @math time @cite_10 @cite_11 . All the results can be parameterized to @math or @math , respectively, where @math is the length of the longest increasing subsequence.