Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#330134] of Alessandro Arlotto

Papers Published

  1. Arlotto, A; Wei, Y; Xie, X, An adaptive O(log n)-optimal policy for the online selection of a monotone subsequence from a random sample, Random Structures and Algorithms, vol. 52 no. 1 (January, 2018), pp. 41-53, Wiley [doi]
    (last updated on 2017/12/11)

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

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320