On the longest increasing subsequence of a circular list. (English) Zbl 1185.68840
Summary: The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time \(O(n^{3/2} \log n)\) and storage requirement \(O(n)\). It is proved that the expected length \(\mu (n)\) of the LICS satisfies \(\lim _{n \rightarrow \infty} \frac {\mu (n)}{2 \sqrt n} = 1\). Numerical experiments with the algorithm suggest that \(|\mu (n) - 2 \sqrt n| = O(n)^{1/6}\).
Software:
MUMMERReferences:
| [1] | Albert, M. H.; Aldred, R. A.; Atkinson, M. D.; van Ditmarsch, H.; Handley, B.; Handley, C. C.; Opatrny, J., Longest subsequences in permutations, Austral. J. Combin., 28, 225-238 (2003) · Zbl 1040.68064 |
| [2] | Albert, M. H.; Golynski, A.; Hamel, A. M.; López-Ortiz, A.; Rao, S. R.; Safari, M. A., Longest increasing subsequences in sliding windows, Theoret. Comput. Sci., 321, 405-414 (2004) · Zbl 1067.68053 |
| [3] | Aldous, D.; Diaconis, P., Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc., 36, 413-432 (1999) · Zbl 0937.60001 |
| [4] | Baer, R. M.; Brock, P., Natural sorting over permutation spaces, Math. Comput., 22, 385-510 (1968) |
| [5] | Baik, J.; Deift, P.; Johansson, K., On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc., 12, 1119-1178 (1999) · Zbl 0932.05001 |
| [6] | Charlebois, R., Organization of the Prokaryotic Genome (1999), ASM Press: ASM Press Washington, DC |
| [7] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press, McGraw-Hill Book Company: MIT Press, McGraw-Hill Book Company New York · Zbl 1158.68538 |
| [8] | Delcher, A. L.; Kasif, S.; Fleischmann, R. D.; Paterson, J.; White, O.; Salzberg, S. L., Alignment of whole genomes, Nucl. Acis Res., 27, 2369-2376 (1999) |
| [9] | Fredman, M. L., On computing the length of longest increasing subsequences, Discrete Math., 11, 29-35 (1975) · Zbl 0312.68027 |
| [10] | Gries, D., The Science of Programming (1981), Springer-Verlag: Springer-Verlag Heidelberg, New York · Zbl 0472.68003 |
| [11] | Manber, U., Introduction to Algorithms (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0825.68397 |
| [12] | Schensted, C., Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191 (1961) · Zbl 0097.25202 |
| [13] | Steele, J. M., Probability Theory and Optimization (1997), SIAM: SIAM New York · Zbl 0916.90233 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
