Constant-Factor Algorithms for Revenue Management with Consecutive Stays

Abstract

Constant-Factor Policies for Consecutive-Stay Bookings Railway operators and hotels must decide whether to accept bookings while preserving capacity for future customers. In “Constant-Factor Algorithms for Revenue Management with Consecutive Stays,” Hu and Wu study this challenge in which requests span consecutive travel legs or nights. The authors develop polynomial-time policies for two settings: one in which a seller accepts or rejects a request and assigns an available resource and another in which customers choose from an assortment under the basic attraction model. When benchmarked against the optimal online policy, the algorithms deliver the first constant-factor revenue guarantees in these settings independent of the maximum stay length. For fixed request types (e.g., their stay intervals are fixed), they guarantee 63.2% of the optimal expected revenue for accept-or-reject decisions and 27.1% under customer choice; for random request types (e.g., their stay intervals are random), the guarantees are 39.9% and 17.1%, respectively. These constant-factor guarantees stand in sharp contrast to the prior nonconstant competitive ratios that are benchmarked against the offline optimum.