Constant-Factor Algorithms for Revenue Management with Consecutive Stays

References

• Adelman D (2007) Dynamic bid prices in revenue management. Oper. Res. 55(4):647–661.Link, Google Scholar
• Agrawal S, Ding Y, Saberi A, Ye Y (2010) Correlation robust stochastic optimization. Proc. 21st ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1087–1096.Google Scholar
• AmaniHamedani A, Aouad A, Saberi A (2025) Adaptive approximation schemes for matching queues. Proc. 57th ACM Sympos. Theory Comput. STOC (ACM, New York), 1454–1464.Google Scholar
• AmaniHamedani A, Aouad A, Pollner T, Saberi A (2024) Improved approximations for stationary bipartite matching: Beyond probabilistic independence. Preprint, submitted November 12, https://doi.org/10.48550/arXiv.2411.08218.Google Scholar
• Anari N, Niazadeh R, Saberi A, Shameli A (2019) Nearly optimal pricing algorithms for production constrained and laminar Bayesian selection. Proc. 2019 ACM Conf. Econom. Comput. (ACM, New York), 91–92.Google Scholar
• Aouad A, Sarıtaç O (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349–2383.Link, Google Scholar
• Arkin EM, Silverberg EB (1987) Scheduling jobs with fixed start and end times. Discrete Appl. Math. 18(1):1–8.Crossref, Google Scholar
• Baek J, Ma W (2022) Bifurcating constraints to improve approximation ratios for network revenue management with reusable resources. Oper. Res. 70(4):2226–2236.Link, Google Scholar
• Balseiro SR, Besbes O, Pizarro D (2024) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Oper. Res. 72(5):2168–2189.Link, Google Scholar
• Bertsimas D, Popescu I (2003) Revenue management in a dynamic network environment. Transportation Sci. 37(3):257–277.Link, Google Scholar
• Bhatia R, Chuzhoy J, Freund A, Naor J (2007) Algorithmic aspects of bandwidth trading. ACM Trans. Algorithms 3(1):1–19.Crossref, Google Scholar
• Braun A, Kesselheim T, Pollner T, Saberi A (2024) Approximating optimum online for capacitated resource allocation. Proc. 25th ACM Conf. Econom. Comput.(ACM, New York), 278–278.Google Scholar
• Braverman M, Derakhshan M, Molina Lovett A (2022) Max-weight online stochastic matching: Improved approximations against the online benchmark. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 967–985.Google Scholar
• Braverman M, Derakhshan M, Pollner T, Saberi A, Wajc D (2025) New philosopher inequalities for online Bayesian matching, via pivotal sampling. Proc. 2025 ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 3029–3068.Google Scholar
• Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Sci. 66(7):2993–3009.Link, Google Scholar
• Chawla S, Miller JB, Teng Y (2019) Pricing for online resource allocation: Intervals and paths. Proc. 30th ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 1962–1981.Google Scholar
• Dütting P, Gergatsouli E, Rezvan R, Teng Y, Tsigonias-Dimitriadis A (2023) Prophet secretary against the online optimal. Proc. 24th ACM Conf. Econom. Comput. (ACM, New York), 561–581.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2024a) Near-optimal Bayesian online assortment of reusable resources. Oper. Res. 72(5):1861–1873.Link, Google Scholar
• Feng Y, Niazadeh R, Saberi A (2024b) Two-stage stochastic matching and pricing with applications to ride hailing. Oper. Res. 72(4):1574–1594.Link, Google Scholar
• Fleischer L, Goemans MX, Mirrokni VS, Sviridenko M (2011) Tight approximation algorithms for maximum separable assignment problems. Math. Oper. Res. 36(3):416–431.Link, Google Scholar
• Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics, vol. 209 (Springer, New York).Crossref, Google Scholar
• Gallego G, Van Ryzin G (1997) A multiproduct dynamic pricing problem and its applications to network yield management. Oper. Res. 45(1):24–41.Link, Google Scholar
• Gallego G, Ratliff R, Shebalov S (2015) A general attraction model and sales-based linear program for network revenue management under customer choice. Oper. Res. 63(1):212–232.Link, Google Scholar
• GlobeNewswire (2025) Railroads industry report 2025: High-speed rail and electrification trends drive railroads market growth, projected to hit $781.2 billion by 2030. Accessed April 3, 2025, https://finance.yahoo.com/news/railroads-industry-report-2025-high-161900682.html?fr=sycsrp_catchall.Google Scholar
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Goyal V, Iyengar G, Udwani R (2025) Asymptotically optimal competitive ratio for online allocation of reusable resources. Oper. Res. 73(4):1897–1915.Link, Google Scholar
• Huang Z, Tang ZG, Wajc D (2024) Online matching: A brief survey. ACM SIGecom Exchanges 22(1):135–158.Crossref, Google Scholar
• Im S, Wang Y (2011) Secretary problems: Laminar matroid and interval scheduling. Proc. 22nd ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 1265–1274.Google Scholar
• Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313–345.Link, Google Scholar
• Jasin S, Kumar S (2013) Analysis of deterministic LP-based booking limit and bid price controls for revenue management. Oper. Res. 61(6):1312–1320.Link, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd ACM Sympos. Theory Comput. STOC (ACM, New York), 352–358.Google Scholar
• Kessel K, Shameli A, Saberi A, Wajc D (2022) The stationary prophet inequality problem. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 243–244.Google Scholar
• Kolen AW, Lenstra JK, Papadimitriou CH, Spieksma FC (2007) Interval scheduling: A survey. Naval Res. Logist. 54(5):530–543.Crossref, Google Scholar
• Kovalyov MY, Ng CT, Cheng TE (2007) Fixed interval scheduling: Models, applications, computational complexity and algorithms. Eur. J. Oper. Res. 178(2):331–342.Crossref, Google Scholar
• Kunnumkal S, Topaloglu H (2010) A new dynamic programming decomposition method for the network revenue management problem with customer choice behavior. Production Oper. Management 19(5):575–590.Crossref, Google Scholar
• Lipton RJ, Tomkins A (1994) Online interval scheduling. Proc. 5th ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 302–311.Google Scholar
• Luce RD (1959) Individual Choice Behavior: A Theoretical Analysis (Wiley, New York).Google Scholar
• Ma W (2024) Randomized rounding approaches to online allocation, sequencing, and matching. Tutorials Oper. Res. Smarter Decisions Better World 2024(October):90–116.Link, Google Scholar
• Ma W, Simchi-Levi D (2020) Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Oper. Res. 68(6):1787–1803.Link, Google Scholar
• Ma W, MacRury C, Zhang J (2024) Online contention resolution schemes for network revenue management and combinatorial auctions. Preprint, submitted December 8, https://doi.org/10.48550/arXiv.2403.05378.Google Scholar
• Ma W, Simchi-Levi D, Zhao J (2021) Dynamic pricing (and assortment) under a static calendar. Management Sci. 67(4):2292–2313.Link, Google Scholar
• Ma Y, Rusmevichientong P, Sumida M, Topaloglu H (2020) An approximation algorithm for network revenue management under nonstationary arrivals. Oper. Res. 68(3):834–855.Link, Google Scholar
• McFadden D (1974) Conditional logit analysis of qualitative choice behavior. Zarembka P, ed. Frontiers in Econometrics (Academic Press, New York), 105–142.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Naor J, Srinivasan A, Wajc D (2025) Online dependent rounding schemes for bipartite matchings, with applications. Proc. 2025 ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 3116–3154.Google Scholar
• Papadimitriou C, Pollner T, Saberi A, Wajc D (2024) Online stochastic max-weight bipartite matching: Beyond prophet inequalities. Math. Oper. Res. 49(3):1607–1628.Link, Google Scholar
• Patel N, Wajc D (2024) Combinatorial stationary prophet inequalities. Proc. 2024 ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 4605–4630.Google Scholar
• Pollner T, Saberi A, Wikum A (2026) Optimal rounding for two-stage bipartite matching. Proc. 2026 ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 5886–5913.Google Scholar
• Reiman MI, Wang Q (2008) An asymptotically optimal policy for a quantity-based network revenue management problem. Math. Oper. Res. 33(2):257–282.Link, Google Scholar
• Rusmevichientong P, Sumida M, Topaloglu H, Bai Y (2023) Revenue management with heterogeneous resources: Unit resource capacities, advance bookings, and itineraries over time intervals. Oper. Res. 71(6):2196–2216.Link, Google Scholar
• Saberi A, Wajc D (2021) The greedy algorithm is not optimal for on-line edge coloring. Bansal N, Merelli E, Worrell J, eds. Proc. 48th Internat. Colloquium Automata Languages Programming ICALP 2021 July 12–16 2021 Glasgow Scotland Virtual Conference, LIPIcs, vol. 198, 109:1–109:18.Google Scholar
• Simchi-Levi D, Zheng Z, Zhu F (2025) On greedy-like policies in online matching with reusable network resources and decaying rewards. Management Sci. 71(10):8908–8926.Link, Google Scholar
• Sun E, Tang ZG, Wang Y (2025) Online stochastic matching with unknown arrival order: Beating 0.5 against the online optimum. Proc. 57th ACM Sympos. Theory Comput. STOC (ACM, New York), 1430–1441.Google Scholar
• Sun E, Tang ZG, Wang Y (2026) Combinatorial philosopher inequalities. Proc. 2026 ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 3872–3904.Google Scholar
• Talluri K, Van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Management Sci. 44(11 Part 1):1577–1593.Link, Google Scholar
• Topaloglu H (2009) Using Lagrangian relaxation to compute capacity-dependent bid prices in network revenue management. Oper. Res. 57(3):637–649.Link, Google Scholar
• Torrico A, Toriello A (2022) Dynamic relaxations for online bipartite matching. INFORMS J. Comput. 34(4):1871–1884.Link, Google Scholar
• Zhang D, Adelman D (2009) An approximate dynamic programming approach to network revenue management with customer choice. Transportation Sci. 43(3):381–394.Link, Google Scholar
• Zhu F, Liu S, Wang R, Wang Z (2023) Assign-to-seat: Dynamic capacity control for selling high-speed train tickets. Manufacturing Service Oper. Management 25(3):921–938.Link, Google Scholar