Quickest online selection of an increasing subsequence of specified size

DOI10.1002/rsa.20634zbMath1347.60042arXiv1412.7985OpenAlexW2265898325MaRDI QIDQ2820269

Alessandro Arlotto, Elchanan Mossel, J. Michael Steele

Publication date: 15 September 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.7985

zbMATH Keywords

dynamic programmingstopping timesMarkov decision problemsequential selectiononline selectionincreasing subsequence problemtime-focused decision problem

Mathematics Subject Classification ID

Dynamic programming in optimal control and differential games (49L20) Dynamic programming (90C39) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stopping times; optimal stopping problems; gambling theory (60G40) Markov and semi-Markov decision processes (90C40)

Related Items (6)

Asymptotic expansions and strategies in the online increasing subsequence problem ⋮ Unnamed Item ⋮ The BRS-inequality and its applications ⋮ Asymptotics and renewal approximation in the online selection of increasing subsequence ⋮ Sequential selection of a monotone subsequence from a random permutation ⋮ On sequential selection and a first passage problem for the Poisson process

Cites Work

• 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
• Optimal sequential selection of a monotone sequence from a random sample
• Level-spacing distributions and the Airy kernel
• Sequential selection of an increasing sequence from a multidimensional random sample.
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• The Surprising Mathematics of Longest Increasing Subsequences
• Markov Decision Problems Where Means Bound Variances
• Optimal Sequential Selection of a Unimodal Subsequence of a Random Sequence
• ‘Wald's Lemma' for sums of order statistics of i.i.d. random variables
• A note on the selection of random variables under a sum constraint
• On the distribution of the length of the longest increasing subsequence of random permutations
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• The Dynamic and Stochastic Knapsack Problem with Deadlines
• Optimal selection of stochastic intervals under a sum constraint
• Sequential selection of an increasing subsequence from a sample of random size

This page was built for publication: Quickest online selection of an increasing subsequence of specified size