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

Jackie Baek () and Will Ma ()
Additional contact information
Jackie Baek: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Will Ma: Graduate School of Business, Columbia University, New York, New York 10027

Operations Research, 2022, vol. 70, issue 4, 2226-2236

Abstract: 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 .

Keywords: Revenue Management and Market Analytics; network revenue management; reusable resources; matroid prophet inequalities; approximate dynamic programming (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2282 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:4:p:2226-2236

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().