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

作者：Arlotto Alessandro^*; Wei Yehua; Xie Xinchang

来源：Random Structures and Algorithms, 2018, 52(1): 41-53.

DOI：10.1002/rsa.20728

• adaptive policy
• dynamic programming
• Markov decision problem
• monotone subsequence
• online selection

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(log?n) of optimal. Our construction provides a direct and natural way for proving the O(log?n)-optimality gap. An earlier proof of the same result made crucial use of a key inequality of Bruss and Delbaen [5] and of de-Poissonization.

• 出版日期2018-1