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.