An adaptive O(log n)‐optimal policy for the online selection of a monotone subsequence from a random sample. Issue 1 (14th August 2017) - Arlotto, Alessandro; Wei, Yehua; Xie, Xinchang
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 ( 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.