Optimal Online Selection of an Alternating Subsequence: A Central Limit Theorem

DOI10.1239/aap/1401369706zbMath1317.60011arXiv1212.1379OpenAlexW2149067909MaRDI QIDQ5169506

J. Michael Steele, Alessandro Arlotto

Publication date: 10 July 2014

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

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

zbMATH Keywords

dynamic programmingBellman equationcentral limit theoremnonhomogeneous Markov chainMarkov decision problemonline selectionalternating subsequence

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial optimization (90C27) Dynamic programming (90C39) Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Markov and semi-Markov decision processes (90C40)

Related Items (3)

Markov Decision Problems Where Means Bound Variances ⋮ Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays ⋮ A Central Limit Theorem for Temporally Nonhomogenous Markov Chains with Applications to Dynamic Programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On the Markov chain central limit theorem
• Time series: theory and methods
• Optimal sequential selection of a monotone sequence from a random sample
• Sequential selection of an increasing sequence from a multidimensional random sample.
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• A Survey of Alternating Permutations
• Optimal Sequential Selection of a Unimodal Subsequence of a Random Sequence
• Online Selection of Alternating Subsequences from a Random Sample
• The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalizations
• Secretary Problems via Linear Programming
• Submodular Secretary Problem and Extensions
• Markov Chains and Stochastic Stability
• A Note on Sequential Selection from Permutations
• Sequential selection of an increasing subsequence from a sample of random size
• Dynamic Programming and Decision Theory

This page was built for publication: Optimal Online Selection of an Alternating Subsequence: A Central Limit Theorem