Online Selection of Alternating Subsequences from a Random Sample

DOI10.1239/jap/1324046022zbMath1258.90103arXiv1105.1558OpenAlexW2150762106MaRDI QIDQ3108479

Alessandro Arlotto, J. Michael Steele, Lawrence A. Shepp, Robert W. Chen

Publication date: 4 January 2012

Published in: Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

Bellman equationsequential selectionprophet inequalityonline selectionalternating subsequence

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Combinatorial probability (60C05) Markov and semi-Markov decision processes (90C40)

Related Items

Markov Decision Problems Where Means Bound Variances, Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays, On-line selection of \(c\)-alternating subsequences from a random sample, Optimal Online Selection of an Alternating Subsequence: A Central Limit Theorem, On the longest \(k\)-alternating subsequence, A Central Limit Theorem for Temporally Nonhomogenous Markov Chains with Applications to Dynamic Programming

Cites Work

• Unnamed Item
• Unnamed Item
• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
• On the limiting distribution for the length of the longest alternating sequence in a random permutation
• Longest alternating subsequences of permutations
• 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
• A Survey of Alternating Permutations
• Sequential selection of an increasing subsequence from a sample of random size