An adaptive O(log n)-optimal policy for the online selection of a monotone subsequence from a random sample
Date
2018-01-01
Authors
Journal Title
Journal ISSN
Volume Title
Repository Usage Stats
views
downloads
Citation Stats
Attention Stats
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.
Type
Department
Description
Provenance
Subjects
Citation
Permalink
Published Version (Please cite this version)
Publication Info
Arlotto, A, Y Wei and X Xie (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). pp. 41–53. 10.1002/rsa.20728 Retrieved from https://hdl.handle.net/10161/33794.
This is constructed from limited available data and may be imprecise. To cite this article, please review & use the official citation provided by the journal.
Collections
Scholars@Duke
Alessandro Arlotto
Alessandro Arlotto is an Associate Professor of Business Administration, Mathematics, and Statistical Science at Duke University. Alessandro holds a primary appointment in the Decision Sciences area of Duke University’s Fuqua School of Business and secondary appointments in the departments of Mathematics and Statistical Science. Alessandro received his Ph.D. in 2012 from the University of Pennsylvania and joined Duke University in the same year.
Alessandro’s research interests are in probability, optimization and their applications to business and economics. His research has appeared in several journals including the Annals of Applied Probability, Management Science, Mathematics of Operations Research, Operations Research, and Stochastic Processes and their Applications. Alessandro is a recipient of the Faculty Early Career Development (CAREER) award from the National Science Foundation.
At Duke, Alessandro teaches the core course Probability and Statistics in the Daytime and Executive MBA programs as well as the Quantitative Business Analysis course for the Master in Management Studies. Alessandro also teaches the graduate course Stochastic Models.
Yehua Wei
Yehua Wei is an associate professor of business administration in Decision Sciences at Fuqua School of Business. Professor Wei received his Ph.D. in Operations Research from MIT in 2013. He taught Decision Models, Spreadsheet Modeling, and Probability & Statistics across different graduate programs. His research interest lies in the broad area of decisions under uncertainty. Specifically, he studies problems in flexibility design, dynamic resource allocation, vehicle routing, queueing networks, strategic routing, and e-commerce fulfillment. His research has been recognized by several awards, including the George Nicholson Paper Competition, Daniel H. Wagner Prize for Excellence in Operations Research Practice, MSOM Service Management SIG Best Paper Prize, and MSOM Practice-Based Research Competition.
Unless otherwise indicated, scholarly articles published by Duke faculty members are made available here with a CC-BY-NC (Creative Commons Attribution Non-Commercial) license, as enabled by the Duke Open Access Policy. If you wish to use the materials in ways not already permitted under CC-BY-NC, please consult the copyright owner. Other materials are made available here through the author’s grant of a non-exclusive license to make their work openly accessible.