Quickest online selection of an increasing subsequence of specified size
From MaRDI portal
Abstract: Given a sequence of independent random variables with a common continuous distribution, we consider the online decision problem where one seeks to minimize the expected value of the time that is needed to complete the selection of a monotone increasing subsequence of a prespecified length . This problem is dual to some online decision problems that have been considered earlier, and this dual problem has some notable advantages. In particular, the recursions and equations of optimality lead with relative ease to asymptotic formulas for mean and variance of the minimal selection time.
Recommendations
- Asymptotic expansions and strategies in the online increasing subsequence problem
- Optimal online selection of a monotone subsequence: a central limit theorem
- Sequential selection of an increasing subsequence from a sample of random size
- Online Selection of Alternating Subsequences from a Random Sample
- An adaptive O( n)-optimal policy for the online selection of a monotone subsequence from a random sample
Cites work
- A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
- A note on the selection of random variables under a sum constraint
- Level-spacing distributions and the Airy kernel
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- Markov decision problems where means bound variances
- On the distribution of the length of the longest increasing subsequence of random permutations
- Optimal online selection of a monotone subsequence: a central limit theorem
- Optimal rules for the sequential selection of monotone subsequences of maximum expected length
- Optimal selection of stochastic intervals under a sum constraint
- Optimal sequential selection of a monotone sequence from a random sample
- Optimal sequential selection of a unimodal subsequence of a random sequence
- Sequential selection of an increasing sequence from a multidimensional random sample.
- Sequential selection of an increasing subsequence from a sample of random size
- The Dynamic and Stochastic Knapsack Problem with Deadlines
- The surprising mathematics of longest increasing subsequences
- ‘Wald's Lemma' for sums of order statistics of i.i.d. random variables
Cited in
(11)- Online Selection of Alternating Subsequences from a Random Sample
- Interactive algorithms: pool, stream and precognitive stream
- An adaptive O( n)-optimal policy for the online selection of a monotone subsequence from a random sample
- Asymptotics and renewal approximation in the online selection of increasing subsequence
- The BRS-inequality and its applications
- Diffusion approximations in the online increasing subsequence problem
- Asymptotic expansions and strategies in the online increasing subsequence problem
- On sequential selection and a first passage problem for the Poisson process
- Sequential selection of an increasing subsequence from a sample of random size
- Sequential selection of a monotone subsequence from a random permutation
- On-line selection of \(c\)-alternating subsequences from a random sample
This page was built for publication: Quickest online selection of an increasing subsequence of specified size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2820269)
