Paper Info
Title
Uniform Loss Algorithms for Online Stochastic Decision-Making With Applications to Bin Packing
Abstract
We consider a general class of finite-horizon online decision-making problems, where in each period a controller is presented a stochastic arrival and must choose an action from a set of permissible actions, and the final objective depends only on the aggregate type-action counts. Such a framework encapsulates many online stochastic variants of common optimization problems including bin packing, generalized assignment, and network revenue management. In such settings, we study a natural model-predictive control algorithm that in each period, acts greedily based on an updated certainty-equivalent optimization problem. We introduce a simple, yet general, condition under which this algorithm obtains uniform additive loss (independent of the horizon) compared to an optimal solution with full knowledge of arrivals. Our condition is fulfilled by the above-mentioned problems, as well as more general settings involving piece-wise linear objectives and offline index policies, including an airline overbooking problem.
Year
DOI
Venue
2020
10.1145/3393691.3394224
SIGMETRICS '20: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems Boston MA USA June, 2020
DocType
ISBN
Citations 
Conference
978-1-4503-7985-4
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Siddhartha Banerjee118522.85
Daniel Freund200.68