Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).
TB8 - RM5: Online algorithms in revenue management
Time:
Tuesday, 28/June/2022:
TB 10:30-12:00
Session Chair: Will Ma
Location:Forum 12
Presentations
Online resource allocation for reusable resources
Wang Chi Cheung, Xilin Zhang
National University of Singapore, Singapore
We study a general model of reusable resource allocation problems. Customers of different types arrive according to a stationary stochastic process. The firm's goal is to maximize multiple kinds of rewards generated by customers. We develop an online policy for deciding on actions to take without knowing the distribution of customer types and show that when the usage duration is small compared with the length of the planning horizon, our policy achieves a near optimal performance.
The multi-secretary problem with many types
Omar Besbes, Yash Kanoria, Akshit Kumar
Columbia Business School, United States of America
We study the multisecretary problem with a capacity to hire up to B out of T candidates with their values drawn i.i.d from a distribution F on [0,1]. We investigate the achievable regret performance where our benchmark is the offline optimal policy. We establish the insufficiency of the common certainty equivalent heuristic for distributions with many types and gaps. We devise a new algorithmic principle called "Conservatism wrt Gaps" and use this to derive near-optimal regret scaling.
Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack
Jiashuo Jiang1, Will Ma2, Jiawei Zhang1
1New York University, United States of America; 2Columbia University, United States of America
Prophet inequalities are a useful tool for designing online allocation procedures and comparing their performance to the optimal offline allocation. In this paper we derive the best-known guarantee for $k$-unit prophet inequalities for all $k>1$. We also provide a tight resolution to the related Magician's problem. Finally, we improve the guarantee from 0.2 to 0.319 for online knapsack, and from 0.321 to 0.3557 for unit-density online knapsack.