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

Journal Article (Academic article)

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 (2001) and of de-Poissonization.

Full Text

Duke Authors

Cited Authors

  • Arlotto, A; Wei, Y; Xie, X

Published Date

  • January 1, 2018

Published In

Volume / Issue

  • 52 / 1

Start / End Page

  • 41 - 53

Published By

International Standard Serial Number (ISSN)

  • 1042-9832

Digital Object Identifier (DOI)

  • 10.1002/rsa.20728