An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals

References

• Adelman D (2007) Dynamic bid prices in revenue management. Oper. Res. 55(4):647–661.Link, Google Scholar
• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• Bertsimas D, Popescu I (2003) Revenue management in a dynamic network environment. Transportation Sci. 37(3):257–277.Link, Google Scholar
• Bront JJM, Mendez Diaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769–784.Link, Google Scholar
• Brown DB, Smith JE (2014) Information relaxations, duality, and convex stochastic dynamic programs. Oper. Res. 62(6):1394–1415.Link, Google Scholar
• Buchbinder N, Naor JS (2009) The design of competitive online algorithms via a primal: Dual approach. Foundations Trends Theoret. Comput. Sci. 3(2–3):93–263.Crossref, Google Scholar
• Chan CW, Farias VF (2009) Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems. Math. Oper. Res. 34(2):333–350.Link, Google Scholar
• Chaneton JM, Vulcano G (2011) Computing bid prices for revenue management under customer choice behavior. Manufacturing Service Oper. Management 13(4):452–470.Link, Google Scholar
• Cooper WL (2002) Asymptotic behavior of an allocation policy for revenue management. Oper. Res. 50(4):720–727.Link, Google Scholar
• Cooper WL, Homem-de-Mello T (2007) Some decomposition methods for revenue management. Transportation Sci. 41(3):332–353.Link, Google Scholar
• Devanur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. Fortnow L, Pu P, eds. Proc. ACM Conf. Electronic Commerce (ACM, New York), 71–78.Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2011) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Chen Y, Roughgarden T, eds. Proc. 12th ACM Conf. Electronic Commerce (ACM, New York), 29–38.Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. de Berg M, Meyer U, eds. Proc. 18th Annual Eur. Conf. Algorithms: Part I (Springer-Verlag, Berlin, Heidelberg), 182–194.Google Scholar
• Gallego G, Iyengar G, Phillips R, Dubey A (2004) Managing flexible products on a network. CORC Technical Report TR-2004-01, Columbia University, New York.Google Scholar
• Gallego G, Li A, Truong VA, Wang X (2016) Online bipartite matching. Working paper, Hong Kong University of Science and Technology, Hong Kong.Google Scholar
• Goel A, Mahdian M, Nazerzadeh H, Saberi A (2010) Advertisement allocation for generalized second-pricing schemes. Oper. Res. Lett. 38(6):571–576.Crossref, Google Scholar
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Hu X, Caldentey R, Vulcano G (2013) Revenue sharing in airline alliances. Managment. Sci. 59(5):1177–1195.Link, 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
• Kesselheim T, Tönnis A, Radke K, Vöcking B (2014) Primal beats dual on online packing LPs in the random-order model. Shmoys D, ed. Proc. 46th Annual ACM Sympos. Theory Comput. (ACM, New York), 303–312.Google Scholar
• Kirshner SN, Nediak M (2015) Scalable dynamic bid prices for network revenue management in continuous time. Production Oper. Management 24(10):1621–1635.Crossref, Google Scholar
• Kunnumkal S, Talluri K (2016a) On a piecewise-linear approximation for network revenue management. Math. Oper. Res. 41(1):72–91.Link, Google Scholar
• Kunnumkal S, Talluri K (2016b) Technical note: A note on relaxations of choice network revenue management dynamic program. Oper. Res. 64(1):158–166.Link, Google Scholar
• Kunnumkal S, Topaloglu H (2008) A refined deterministic linear program for the network revenue management problem with customer choice behavior. Naval Res. Logist. Quart. 55(6):563–580.Crossref, Google Scholar
• Kunnumkal S, Topaloglu H (2010a) Computing time-dependent bid prices in network revenue management problems. Transportation Sci. 44(1):38–62.Link, Google Scholar
• Kunnumkal S, Topaloglu H (2010b) 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
• Liu Q, van Ryzin GJ (2008) On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2):288–310.Link, Google Scholar
• Maglaras C, Meissner J (2006) Dynamic pricing strategies for multiproduct revenue management problems. Manufacturing Service Oper. Management 8(2):136–148.Link, Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5)22:1–22:19.Google Scholar
• Meissner J, Strauss A, Talluri K (2012) An enhanced concave program relaxation for choice network revenue management. Production Oper. Management 22(1):71–87.Crossref, Google Scholar
• Mendez-Diaz I, Bront JJM, Vulcano G, Zabala P (2010) A branch-and-cut algorithm for the latent-class logit assortment problem. Discrete Appl. Math. 36:383–390.Google Scholar
• Molinaro M, Ravi R (2014) The geometry of online packing linear programs. Math. Oper. Res. 39(1):46–59.Link, Google Scholar
• Rusmevichientong P, Sumida M, Topaloglu H (2020) Dynamic assortment optimization for reusable products with random usage durations. Management Sci. ePub ahead of print January 29, https://doi.org/10.1287/mnsc.2019.3346.Google Scholar
• Simpson RW (1989) Using Network Flow Techniques to Find Shadow Prices for Market Demands and Seat Inventory Control (MIT Press, Cambridge, MA).Google Scholar
• Strauss AK, Talluri K (2017) Tractable consideration set structures for network revenue management. Production Oper. Management 26(7):1359–1368.Crossref, Google Scholar
• Talluri K (2014) New formulations for choice network revenue management. INFORMS J. Comput. 26(2):401–413.Link, Google Scholar
• Talluri KT, van Ryzin GJ (1998) An analysis of bid-price controls for network revenue management. Management Sci. 44(11-part-1):1577–1593.Google Scholar
• Talluri KT, van Ryzin GJ (1999) A randomized linear programming method for computing network bid prices. Transportation Sci. 33(2):207–216.Link, Google Scholar
• Talluri KT, van Ryzin GJ (2005) The Theory and Practice of Revenue Management (Kluwer Academic Publishers, Boston).Crossref, Google Scholar
• Tan B, Srikant R (2012) Online advertisement, optimization and stochastic networks. IEEE Trans. Automatic Control 57(11):2854–2868.Crossref, Google Scholar
• Tong C, Topaloglu H (2013) On the approximate linear programming approach for network revenue management problems. INFORMS J. Comput. 26(1):121–134.Link, Google Scholar
• Topaloglu H (2008) A stochastic approximation method to compute bid prices in network revenue management problems. INFORMS J. Comput. 20(4):596–610.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
• van Ryzin G, Vulcano G (2008a) Computing virtual nesting controls for network revenue management under customer choice behavior. Manufacturing Service Oper. Management 10(3):448–467.Link, Google Scholar
• van Ryzin G, Vulcano G (2008b) Simulation-based optimization of virtual nesting controls for network revenue management. Oper. Res. 56(4):865–880.Link, Google Scholar
• Vossen TWM, Zhang D (2015a) A dynamic disaggregation approach to approximate linear programs for network revenue management. Production Oper. Management 24(3):469–487.Crossref, Google Scholar
• Vossen TWM, Zhang D (2015b) Reductions of approximate linear programs for network revenue management. Oper. Res. 63(6):1352–1371.Link, Google Scholar
• Wang X, Truong VA, Bank D (2016) Online advance admission scheduling for services, with customer preferences. Working paper, Columbia University, New York.Google Scholar
• Williamson EL (1992) Airline network seat control. PhD thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Zhang D (2011) An improved dynamic programming decomposition approach for network revenue management. Manufacturing Service Oper. Management 13(1):35–52.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
• Zhang D, Cooper WL (2009) Pricing substitutable flights in airline revenue management. Eur. J. Oper. Res. 197(3):848–861.Crossref, Google Scholar