Increasing and other subsequence problems for random interval sequences
Preprint
Abstract
Various relations for comparison of intervals of real numbers are introduced, and the expected length of the corresponding longest increasing subsequence is analyzed. When intervals are randomly generated by taking the minimum and maximum of two independent uniform random variables, we prove that the expected length of the longest increasing subsequence grows on the order of 3 √ n. We also investigate the asymptotic behavior of the expected length under alternative comparison relations and random interval models. Discussions on other subsequence problems for interval sequences are included.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- The Surprising Mathematics of Longest Increasing Subsequences2014
- Concentration of Measure for the Analysis of Randomized Algorithms2009
- Normal approximation under local dependenceThe Annals of Probability, 2004
- On longest increasing subsequences in random permutations2000
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theoremBulletin of the American Mathematical Society, 1999
- On the distribution of the length of the longest increasing subsequence of random permutationsJournal of the American Mathematical Society, 1999
- Probability Theory and Combinatorial Optimization1997
- Random interval graphsCombinatorica, 1988