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

Math @ Duke



Publications [#319307] of Alessandro Arlotto

Papers Published

  1. Arlotto, A; Steele, JM, Optimal sequential selection of a unimodal subsequence of a random sequence, Combinatorics, Probability and Computing, vol. 20 no. 06 (November, 2011), pp. 799-814, Cambridge University Press (CUP) [doi]
    (last updated on 2021/07/30)

    We consider the problem of selecting sequentially a unimodal subsequence from a sequence of independent identically distributed random variables, and we find that a person doing optimal sequential selection does so within a factor of the square root of two as well as a prophet who knows all of the random observations in advance of any selections. Our analysis applies in fact to selections of subsequences that have d+1 monotone blocks, and, by including the case d=0, our analysis also covers monotone subsequences. © 2011 Cambridge University Press.
ph: 919.660.2800
fax: 919.660.2821

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