An adaptive O( n)-optimal policy for the online selection of a monotone subsequence from a random sample

DOI10.1002/RSA.20728MaRDI QIDQ4601440zbMATH OpenOpenAlexWikidataFDO

Authors Alessandro Arlotto, Yehua Wei, Xinchang Xie

Publication date 16 January 2018

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

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

zbMATH Keywords

dynamic programmingadaptive policyMarkov decision problemmonotone subsequenceonline selection

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: Given a sequence of $n$ independent random variables with common continuous distribution, we propose a simple adaptive online policy that selects a monotone increasing subsequence. We show that the expected number of monotone increasing selections made by such a policy is within $O(logn)$ of optimal. Our construction provides a direct and natural way for proving the $O(logn)$-optimality gap. An earlier proof of the same result made crucial use of a key inequality of Bruss and Delbaen (2001) and of de-Poissonization.

Recommendations

• Optimal online selection of a monotone subsequence: a central limit theorem
• Quickest online selection of an increasing subsequence of specified size
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• Sequential selection of an increasing subsequence from a sample of random size
• Optimal online selection of an alternating subsequence: a central limit theorem

Cited in

(12)

• Online Selection of Alternating Subsequences from a Random Sample
• Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
• Optimal online selection of an alternating subsequence: a central limit theorem
• 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
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• Quickest online selection of an increasing subsequence of specified size
• 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
• On-line selection of \(c\)-alternating subsequences from a random sample

This page was built for publication: An adaptive \(O(\log n)\)-optimal policy for the online selection of a monotone subsequence from a random sample

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601440)