Survey of Dynamic Resource-Constrained Reward Collection Problems: Unified Model and Analysis

References

• Abhishek V, Hosanagar K (2013) Optimal bidding in multi-item multislot sponsored search auctions. Oper. Res. 61(4):855–873.Link, Google Scholar
• Acimovic J, Farias VF (2019) The fulfillment-optimization problem. Netessine S, ed. Operations Research & Management Science in the Age of Analytics. TutORials in Operations Research (INFORMS, Catonsville, MD), 218–237.Link, Google Scholar
• Acimovic J, Graves SC (2015) Making better fulfillment decisions on the fly in an online retail environment. Manufacturing Service Oper. Management 17(1):34–51.Link, Google Scholar
• Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1253–1264.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
• Andrews JM, Farias VF, Khojandi AI, Yan CM (2019) Primal–dual algorithms for order fulfillment at Urban Outfitters, Inc. Interfaces 49(5):355–370.Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Arlotto A, Xie X (2020) Logarithmic regret in the dynamic and stochastic knapsack problem. Stochastic Systems 10(2):170–191.Link, Google Scholar
• Asadpour A, Wang X, Zhang J (2020) Online resource allocation with limited flexibility. Management Sci. 66(2):642–666.Link, Google Scholar
• Badanidiyuru A, Kleinberg R, Slivkins A (2013) Bandits with knapsacks. Proc. IEEE 54th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 207–216.Crossref, Google Scholar
• Badanidiyuru A, Langford J, Slivkins A (2014) Resourceful contextual bandits. Balcan MF, Feldman V, Szepesvári C, eds. Proc. 27th Conf. Learning Theory (Microtome Publishing, Brookline, MA), 1109–1134.Google Scholar
• Balseiro SR, Besbes O, Weintraub GY (2015) Repeated auctions with budgets in ad exchanges: Approximations and design. Management Sci. 61(4):864–884.Link, Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2023) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Bernstein F, Gürhan Kök A, Xie L (2015) Dynamic assortment customization with limited inventories. Manufacturing Service Oper. Management 17(4):538–553.Link, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, vol. 6 (Athena Scientific, Belmont, MA).Google Scholar
• Besbes O, Zeevi A (2009) Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Oper. Res. 57(6):1407–1420.Link, Google Scholar
• Bitran G, Caldentey R (2003) An overview of pricing models for revenue management. Manufacturing Service Oper. Management 5(3):203–229.Link, Google Scholar
• Bray RL (2022) Logarithmic regret in multisecretary and online linear programming problems with continuous valuations. Working paper, Northwestern University, Evanston, IL.Google Scholar
• Bront JJM, Méndez-Díaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769–784.Link, Google Scholar
• Bubeck S (2014) Convex optimization: Algorithms and complexity. Preprint, submitted May 20, https://arxiv.org/abs/1405.4980.Google Scholar
• Bubeck S, Cesa-Bianchi N (2012) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Preprint, submitted April 25, https://arxiv.org/abs/1204.5721.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
• Devanur NR, Jain K, Kleinberg RD (2013) Randomized primal-dual analysis of ranking for online bipartite matching. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 101–107.Google Scholar
• D’Sylva E (1982) O and D seat assignment to maximize expected revenue. Unpublished internal report, Boeing Commercial Airplane Company, Seattle.Google Scholar
• Erdelyi A, Topaloglu H (2011) Using decomposition methods to solve pricing problems in network revenue management. J. Revenue Pricing Management 10(4):325–343.Crossref, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 117–126.Google Scholar
• Fernandez-Tapia J, Guéant O, Lasry JM (2017) Optimal real-time bidding strategies. Appl. Math. Res. eXpress 2017(1):142–183.Google Scholar
• Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics. International Series in Operations Research & Management Science, 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, Iyengar G, Phillips R, Dubey A (2020) Managing flexible products on a network. Preprint, submitted April 27, http://dx.doi.org/10.2139/ssrn.3567371.Google Scholar
• Glover F, Glover R, Lorenzo J, McMillan C (1982) The passenger-mix problem in the scheduled airlines. Interfaces 12(3):73–80.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
• Harsha P, Subramanian S, Uichanco J (2019) Dynamic pricing of omnichannel inventories. Manufacturing Service Oper. Management 21(1):47–65.Link, Google Scholar
• Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optimization 2(3–4):157–325.Crossref, Google Scholar
• Jasin S (2014) Reoptimization and self-adjusting price control for network revenue management. Oper. Res. 62(5):1168–1178.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, Sinha A (2015) An LP-based correlated rounding scheme for multi-item ecommerce order fulfillment. Oper. Res. 63(6):1336–1351.Link, Google Scholar
• Kakade S, Shalev-Shwartz S, Tewari A (2009) On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Working paper, Harvard University, Cambridge, MA.Google Scholar
• Karlin S (1962) Stochastic models and optimal policy for selling an asset. Arrow KJ, Karlin S, Scarf HE, eds. Studies in Applied Probability and Management Science (Stanford University Press, Stanford, CA), 148–158.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 630–631.Google Scholar
• Kleywegt AJ, Papastavrou JD (1998) The dynamic and stochastic knapsack problem. Oper. Res. 46(1):17–35.Link, Google Scholar
• Kunnumkal S, Topaloglu H (2010) A stochastic approximation algorithm for making pricing decisions in network revenue management problems. J. Revenue Pricing Management 9(5):419–442.Crossref, Google Scholar
• Lei Y(M), Jasin S, Sinha A (2018) Joint dynamic pricing and order fulfillment for e-commerce retailers. Manufacturing Service Oper. Management 20(2):269–284.Link, Google Scholar
• Lei Y(M), Jasin S, Uichanco J, Vakhutinsky A (2021) Joint product framing (display, ranking, pricing) and order fulfillment under the multinomial logit model for e-commerce retailers. Manufacturing Service Oper. Management 24(3):1529–1546.Google Scholar
• Li X, Ye Y (2022) Online linear programming: Dual convergence, new algorithms, and regret bounds. Oper. Res. 70(5):2948–2966.Link, Google Scholar
• Liu Q, Van Ryzin G (2008) On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2):288–310.Link, Google Scholar
• Lueker GS (1998) Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2):277–305.Crossref, 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
• Maglaras C, Meissner J (2006) Dynamic pricing strategies for multiproduct revenue management problems. Manufacturing Service Oper. Management 8(2):136–148.Link, Google Scholar
• Mahdian M, Nazerzadeh H, Saberi A (2012) Online optimization with uncertain information. ACM Trans. Algorithms 8(1):1–29.Crossref, Google Scholar
• Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573.Link, Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Milgrom P, Segal I (2002) Envelope theorems for arbitrary choice sets. Econometrica 70(2):583–601.Crossref, Google Scholar
• Mirrokni VS, Gharan SO, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1690–1701.Google Scholar
• Papastavrou JD, Rajagopalan S, Kleywegt AJ (1996) The dynamic and stochastic knapsack problem with deadlines. Management Sci. 42(12):1706–1718.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
• Sakaguchi M, Saario V (1995) A class of best-choice problems with full information. Mathematica Japonicae 41(2):389–398.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
• Talluri K, Van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15–33.Link, Google Scholar
• Talluri KT, Van Ryzin GJ (2006) The Theory and Practice of Revenue Management. International Series in Operations Research & Management Science, vol. 68 (Springer, New York).Google Scholar
• Vera A, Arlotto A, Gurvich I, Levin E (2020) Dynamic resource allocation: The geometry and robustness of constant regret. Working paper, Northwestern University, Evanston, IL.Google Scholar
• Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar
• Vera A, Banerjee S, Gurvich I (2021) Online allocation and pricing: Constant regret via Bellman inequalities. Oper. Res. 69(3):821–840.Link, Google Scholar
• Wang KW (1983) Optimum seat allocation for multi-leg flights with multiple fare types. AGIFORS 23rd Annual Sympos. (Airline Group of the International Federation of Operational Research Societies, Atlanta), 225–246.Google Scholar
• Wang Y, Wang H (2022) Constant regret re-solving heuristics for price-based revenue management. Oper. Res. 70(6):3538–3557.Link, Google Scholar
• Wu H, Srikant R, Liu X, Jiang C (2015) Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Cortes C, Lee DD, Sugiyama M, Garnett R, eds. Proc. 28th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 433–441.Google Scholar