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 (n3 / 2 log n) and storage requirement O (n). It is proved that the expected length μ (n) of the LICS satisfies limn → ∞ frac(μ (n), 2 sqrt(n)) = 1. Numerical experiments with the algorithm suggest that | μ (n) - 2 sqrt(n) | = O (n1 / 6).

Additional Metadata
Keywords Combinatorial problems, Randomized algorithms
Persistent URL dx.doi.org/10.1016/j.ipl.2006.08.003
Journal Information Processing Letters
Citation
Albert, M.H., Atkinson, M.D., Nussbaum, D, Sack, J.-R, & Santoro, N. (2007). On the longest increasing subsequence of a circular list. Information Processing Letters, 101(2), 55–59. doi:10.1016/j.ipl.2006.08.003