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

In the network revenue management (NRM) problem, "itineraries" consisting of capacity-constrained "legs" are sold to a stream of online demand. Approximate dynamic programming (ADP) and prophet inequalities represent two broad methods for deriving approximation algorithms for NRM, and in this paper we dissect their pros and cons. If every itinerary uses at most L legs, then ADP guarantees a 1/(1+L)-approximation. If the legs correspond to the availabilities of reusable resources over time, then a 1/2-approximation is known, but only for L=1. Meanwhile, prophet inequalities guarantee a 1/2-approximation when the capacity constraints follow a matroid structure, but they cannot handle reusable resources. Accordingly, we propose a policy which "bifurcates" the capacity constraints, and uses each method to handle its specialties. Our guarantee is 1/(2(1+L')) under both matroid constraints and other capacity constraints from which each itinerary uses at most L' capacities; we note that L' could be much smaller than L. Our guarantee generalizes to reusable resources, choice models, and improves to 1/(1+L') with the matroid constraint removed. We conduct simulations on NRM instances containing legs corresponding to a sequence of "add-ons", which satisfies the matroid structure. We find that bifurcating the add-on constraints always improves the empirical performance, and moreover, the improvement from bifurcation is linear in the number of add-ons, which is consistent with our improvement in theoretical guarantee. Whereas existing work has proposed one-size-fits-all methods that handle all the constraints generically, our paper demonstrates the benefit of analyzing network structure and using different methods to handle different constraints.