Dynamic Resource Allocation: Algorithmic Design Principles and Spectrum of Achievable Performances
研究动态资源分配问题中请求类型分布与算法性能的关系，提出一种基于模拟的算法，在多种配置下都能接近最优性能。
In “Dynamic Resource Allocation: Algorithmic Design Principles and Spectrum of Achievable Performances,” O. Besbes, Y. Kanoria, and A. Kumar consider a broad class of dynamic resource allocation problems and study the performance of practical algorithms. In particular, they focus on the interplay between the distribution of request types and achievable performance, given the broad set of configurations that can be encountered in practical settings. Although prior literature studied either a small number of request types or a continuum of types with no gaps, the present work allows for a large class of type distributions. Using initially the prototypical multisecretary problem to explore fundamental performance limits as a function of type distribution properties, the authors develop a new algorithmic property “conservativeness with respect to gaps” that guarantees near-optimal performance. In turn, they introduce a practically motivated, simulation-based algorithm and establish its near-optimal performance, not only for multisecretary problems, but also for general dynamic resource allocation problems.