Technical Note—Bifurcating Constraints to Improve Approximation Ratios for Network Revenue Management with Reusable Resources.

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. Network revenue management (NRM) describes a general online allocation problem in which combinations of capacity-constrained resources are sold to a stream of arriving customers. Existing papers propose one-size-fits-all methods for controlling the resource capacities over time. In this paper, we study how different methods can be used to control different resource constraints based on the network structure of each instance. Specifically, we propose a heuristic that "bifurcates" the resources of a given NRM instance into a structured part resembling a matroid and an unstructured part. We then derive an NRM policy with an approximation ratio of 1 / (2 (1 + L ′)) , where L ′ denotes the maximum number of distinct unstructured resources required by a customer. Our approach improves theoretical and empirical performance both in applications where the structured constraints arise naturally and in randomly generated NRM instances where the structured constraints must be found by our heuristic. Along the way, our paper also provides a unified framework for analyzing NRM problems, which simplifies existing results and allows for the resources to be reusable. [ABSTRACT FROM AUTHOR]