An adaptive O(log n)‐optimal policy for the online selection of a monotone subsequence from a random sample. Issue 1 (14th August 2017)

• Record Type: Journal Article
• Authors: Arlotto, Alessandro; Wei, Yehua; Xie, Xinchang
• Is Part Of: Random structures & algorithms. Volume 52:Issue 1(2018)
• Page Start: 41
• Page End: 53
• Publication Date: 2017-08-14
• Subjects: adaptive policy -- dynamic programming -- Markov decision problem -- monotone subsequence -- online selection; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20728
• Languages: English
• ISSNs: 1042-9832

Abstract

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.