| Session | ||
TB8 - RM5: Online algorithms in revenue management
| ||
| Presentations | ||
Online resource allocation for reusable resources 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 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 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. | ||