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

Alessandro Arlotto, Yehua Wei, Xinchang Xie

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.…