An adaptive O(log n)-optimal policy for the online selection of a monotone subsequence from a random sample
Publication
, Journal Article
Arlotto, A; Wei, Y; Xie, X
Published in: Random Structures and Algorithms
January 1, 2018
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.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Random Structures and Algorithms
DOI
ISSN
1042-9832
Publication Date
January 1, 2018
Volume
52
Issue
1
Start / End Page
41 / 53
Publisher
Wiley
Related Subject Headings
- Computation Theory & Mathematics
- 4904 Pure mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0104 Statistics
- 0101 Pure Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Arlotto, A., Wei, Y., & Xie, X. (2018). An adaptive O(log n)-optimal policy for the online selection of a monotone subsequence from a random sample. Random Structures and Algorithms, 52(1), 41–53. https://doi.org/10.1002/rsa.20728
Arlotto, A., Y. Wei, and X. Xie. “An adaptive O(log n)-optimal policy for the online selection of a monotone subsequence from a random sample.” Random Structures and Algorithms 52, no. 1 (January 1, 2018): 41–53. https://doi.org/10.1002/rsa.20728.
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. 2018 Jan 1;52(1):41–53.
Arlotto, A., et al. “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, Wiley, Jan. 2018, pp. 41–53. Manual, doi:10.1002/rsa.20728.
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. Wiley; 2018 Jan 1;52(1):41–53.
Published In
Random Structures and Algorithms
DOI
ISSN
1042-9832
Publication Date
January 1, 2018
Volume
52
Issue
1
Start / End Page
41 / 53
Publisher
Wiley
Related Subject Headings
- Computation Theory & Mathematics
- 4904 Pure mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0104 Statistics
- 0101 Pure Mathematics