Dynamic Allocation of Reusable Resources: Logarithmic Regret in Overloaded Networks
研究了酒店、租车等服务场景中，如何在有限容量下动态分配可重用资源，提出一个简单有效的算法，其性能损失随系统规模增大呈对数增长，对大规模系统几乎最优。
How to dynamically allocate limited capacity to service requests? The problem studied in this paper is common in service applications, such as hotels, car rentals, and consulting services. These applications have limited capacity that must be allocated among incoming service requests. Different requests may require resources for varying durations, and some requests might yield higher rewards than others when fulfilled. The decision maker, who controls this capacity, must decide upon each request’s arrival whether to accept it (thus committing resources for a certain period) or reject it in order to reserve capacity for potentially more valuable future requests. This paper expands our understanding of such resource allocation problems by developing an appealingly simple dynamic allocation algorithm with proven effectiveness. In an appropriate operating regime, the suboptimal gap of this algorithm is at most logarithmic in the maximum achievable reward. In other words, for large-scale systems, the suboptimality translates to a negligible percentage deviation from optimal performance. Paper’s Title: Dynamic Allocation of Reusable Resources: Logarithmic Regret in Overloaded Networks