Optimal online selection of a monotone subsequence: a central limit theorem

DOI10.1016/j.spa.2015.03.009zbMath1327.60053arXiv1408.6750OpenAlexW2004912523WikidataQ29301140 ScholiaQ29301140MaRDI QIDQ491928

Alessandro Arlotto, J. Michael Steele, Vinh V. Nguyen

Publication date: 19 August 2015

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingBellman equationcentral limit theoremmartingaleMarkov decision problemmonotone subsequencenon-homogeneous Markov chainoptimal online selection

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) 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) Functional limit theorems; invariance principles (60F17)

Related Items

A unified approach for solving sequential selection problems ⋮ Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ Online Scheduling with Increasing Subsequence Serving Constraint ⋮ On-line Scheduling with a Monotonous Subsequence Constraint ⋮ Asymptotic expansions and strategies in the online increasing subsequence problem ⋮ The BRS-inequality and its applications ⋮ Asymptotics and renewal approximation in the online selection of increasing subsequence ⋮ Diffusion approximations in the online increasing subsequence problem ⋮ Quickest online selection of an increasing subsequence of specified size ⋮ Sequential selection of a monotone subsequence from a random permutation ⋮ On-line scheduling with monotone subsequence constraints

Cites Work

• Unnamed Item
• 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
• Descending subsequences of random permutations
• Analytical depoissonization and its applications
• Optimal sequential selection of a monotone sequence from a random sample
• The height of a random partial order: Concentration of measure
• Subadditive ergodic theory
• A variational problem for random Young tableaux
• Dependent central limit theorems and invariance principles
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• On increasing subsequences of random permutations
• 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
• Tauberian Theory
• Sequential selection of an increasing subsequence from a sample of random size
• Martingale Central Limit Theorems

This page was built for publication: Optimal online selection of a monotone subsequence: a central limit theorem