Technical Note—Bifurcating Constraints to Improve Approximation Ratios for Network Revenue Management with Reusable Resources
Baek和Ma提出了一个统一框架，用于在一般网络收益管理环境中动态分配可重用资源，允许每个请求占用任意资源组合和不同时长，并设计了简单算法，在理论上和实证上均优于现有方法。
In “Bifurcating Constraints to Improve Approximation Ratios for Network Revenue Management with Reusable Resources,” Baek and Ma provide a unified framework for dynamically allocating reusable resources over time in the general network revenue management setting. That is, each incoming query is allowed to request an arbitrary combination of resources for different unknown durations, capturing applications like cloud computing and the dispatching of human resources. Through this framework, they derive simple algorithms that achieve the same approximation ratios as existing algorithms, which only allow queries to request one resource. Their framework also suggests a meta-algorithm for “bifurcating” the resources depending on the network structure and then using two different algorithms for controlling the capacities of two different groups of resources. This contrasts existing “one-size-fits-all” approaches to network revenue management and is demonstrated to improve both theoretical guarantees and empirical performance over a wide variety of instances.