Math @ Duke

Publications [#330134] of Alessandro Arlotto
Papers Published
 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 & Algorithms, vol. 52 no. 1
(January, 2018),
pp. 4153, Wiley [doi]
(last updated on 2018/10/20)
Abstract: © 2017 Wiley Periodicals, Inc. 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 (Figure presented.) of optimal. Our construction provides a direct and natural way for proving the (Figure presented.) optimality gap. An earlier proof of the same result made crucial use of a key inequality of Bruss and Delbaen [5] and of dePoissonization.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

