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

References

• Adelman D (2007) Dynamic bid prices in revenue management. Oper. Res. 55(4):647–661.Link, Google Scholar
• Baek J, Ma W (2019) Prophet inequalities on the intersection of a matroid and a graph. Sympos. Algorithmic Game Theory (SAGT) (Springer, Cham), 393.Google Scholar
• Bertsimas D, Popescu I (2003) Revenue management in a dynamic network environment. Transportation Sci. 37(3):257–277.Link, Google Scholar
• Besbes O, Elmachtoub AN, Sun Y (2020) Pricing analytics for rotable spare parts. INFORMS J. Appl. Analytics 50(5):313–324.Link, Google Scholar
• Besbes O, Elmachtoub AN, Sun Y (2021) Static pricing: Universal guarantees for reusable resources. Oper. Res., ePub ahead of print March 11, https://doi.org/10.1287/opre.2020.2054.Link, 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
• Cheung WC, Simchi-Levi D (2016) Efficiency and performance guarantees for choice-based network revenue management problems with flexible products. Preprint, submitted August 15, http://dx.doi.org/10.2139/ssrn.2823339.Google Scholar
• Dai J, Kleywegt AJ, Xiao Y (2019) Network revenue management with cancellations and no-shows. Production Oper. Management 28(2):292–318.Crossref, Google Scholar
• Delong S, Farhadi A, Niazadeh R, Sivan B (2021) Online bipartite matching with reusable resources. Preprint, submitted October 13, https://arxiv.org/abs/2110.07084.Google Scholar
• DeValve L, Pekeč S, Wei Y (2020) A primal-dual approach to analyzing ato systems. Management Sci. 66(11):5389–5407.Link, Google Scholar
• DeValve L, Pekeč S, Wei Y (2021) Approximate submodularity in network design problems. Preprint, submitted May 13, http://dx.doi.org/10.2139/ssrn.3844987.Google Scholar
• Dickerson JP, Sankararaman KA, Srinivasan A, Xu P (2018) Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. 32nd AAAI Conf. Artificial Intelligence.Google Scholar
• Düetting P, Feldman M, Kesselheim T, Lucier B (2017) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. 2017 IEEE 58th Annual Sympos. Foundations Comput. Science (FOCS) (IEEE), 540–551.Google Scholar
• Farias VF, Van Roy B (2007) An approximate dynamic programming approach to network revenue management. Preprint, submitted. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.127.8583&rep=rep1&type=pdf.Google Scholar
• Feldman M, Gravin N, Lucier B (2014) Combinatorial auctions via posted prices. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 123–135.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2020) Near-optimal Bayesian online assortment of reusable resources. Chicago Booth Research Paper No. 20-40, University of Chicago, Chicago.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2021) Online assortment of reusable resources with exogenous replenishment. Preprint, submitted March 2, http://dx.doi.org/10.2139/ssrn.3795056.Google Scholar
• Gallego G, Topaloglu H (2018) Revenue Management and Pricing Analytics (Springer, Berlin).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
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Gong XY, Goyal V, Iyengar GN, Simchi-Levi D, Udwani R, Wang S (2021) Online assortment optimization with reusable resources. Management Sci., ePub ahead of print November 11, https://doi.org/10.1287/mnsc.2021.4134.Link, Google Scholar
• Goyal V, Iyengar G, Udwani R (2020) Online allocation of reusable resources: Achieving optimal competitive ratio. Preprint, submitted October 8, https://arxiv.org/abs/2002.02430v3.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
• Jiang J, Wang S, Zhang J (2019) Achieving high individual service-levels without safety stock? Optimal rationing policy of pooled resources. Optimal rationing policy of pooled resources. NYU Stern School of Business working paper, New York University, New York.Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136.Google Scholar
• Korte B, Vygen J (2006) Combinatorial Optimization, 3rd ed. (Springer, Berlin).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
• Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. Preprint, submitted June 25, https://arxiv.org/abs/1806.09251.Google Scholar
• Lei Y, Jasin S (2020) Real-time dynamic pricing for revenue management with reusable resources, advance reservation, and deterministic service time requirements. Oper. Res. 68(3):676–685.Link, Google Scholar
• Liu N, Truong VA, Wang X, Anderson BR (2019) Integrated scheduling and capacity planning with considerations for patients’ length-of-stays. Production Oper. Management 28(7):1735–1756.Crossref, Google Scholar
• Lu L, Song JS, Zhang H (2015) Optimal and asymptotically optimal policies for assemble-to-order n-and w-systems. Naval Res. Logist. 62(8):617–645.Crossref, 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
• Manshadi V, Rodilitz S (2022) Online policies for efficient volunteer crowdsourcing. Management Sci., ePub ahead of print January 25, https://doi.org/10.1287/mnsc.2021.4220.Link, 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 (2020) Dynamic assortment optimization for reusable products with random usage durations. Management Sci. 66(7):2820–2844.Link, 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
• Vossen TW, Zhang D (2015) Reductions of approximate linear programs for network revenue management. Oper. Res. 63(6):1352–1371.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
• Zhang D, Cooper WL (2005) Revenue management for parallel flights with customer-choice behavior. Oper. Res. 53(3):415–431.Link, Google Scholar