Sequential selection of a monotone subsequence from a random permutation
DOI10.1090/proc/13104zbMath1386.60038arXiv1509.04617OpenAlexW2269547337MaRDI QIDQ2821757
Peichao Peng, J. Michael Steele
Publication date: 23 September 2016
Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.04617
Markov decision problemmonotone subsequence problemsequential selectionprophet inequalitynonlinear recursiononline selection
Dynamic programming (90C39) Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Markov and semi-Markov decision processes (90C40)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Optimal online selection of a monotone subsequence: a central limit theorem
- A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
- Online algorithms. The state of the art
- Stochastic optimal control. The discrete time case
- Optimal sequential selection of a monotone sequence from a random sample
- Optimal rules for the sequential selection of monotone subsequences of maximum expected length
- Quickest online selection of an increasing subsequence of specified size
- The Surprising Mathematics of Longest Increasing Subsequences
- ‘Wald's Lemma' for sums of order statistics of i.i.d. random variables
- On the distribution of the length of the longest increasing subsequence of random permutations
- Optimal selection of stochastic intervals under a sum constraint
- A Note on Sequential Selection from Permutations
- Sequential selection of an increasing subsequence from a sample of random size
- The Bruss-Robertson Inequality:Elaborations, Extensions, and Applications
This page was built for publication: Sequential selection of a monotone subsequence from a random permutation
