Dynamic Resource Allocation: Algorithmic Design Principles and Spectrum of Achievable Performances

References

• Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• Aouad A, Ma W (2022) A nonparametric framework for online stochastic matching with correlated arrivals. Preprint, submitted August 3, https://arxiv.org/abs/2208.02229.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 with equal rewards. Stochastic Systems 10(2):170–191.Link, Google Scholar
• Bai Y, El Housni O, Jin B, Rusmevichientong P, Topaloglu H, Williamson DP (2023) Fluid approximations for revenue management under high-variance demand. Management Sci 69(7):4016–4026.Link, Google Scholar
• Balseiro SR, Besbes O, Pizarro D (2023) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Oper. Res 72(5):2168–2189.Link, Google Scholar
• Balseiro S, Kroer C, Kumar R (2022) Online resource allocation under horizon uncertainty. Preprint, submitted June 27, https://arxiv.org/abs/2206.13606.Google Scholar
• Besbes O, Sauré D (2014) Dynamic pricing strategies in the presence of demand shifts. Manufacturing Service Oper. Management 16(4):513–528.Link, Google Scholar
• Blumrosen L, Holenstein T (2008) Posted prices vs. negotiations: An asymptotic analysis. Proc. 9th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York).Google Scholar
• Bray RL (2022) Logarithmic regret in multisecretary and online linear programming problems with continuous valuations. Preprint, submitted December 16, https://arxiv.org/abs/1912.08917.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
• Cayley A (1875) Mathematical questions with their solutions. Ed Times 23:18–19.Google Scholar
• Chawla S, Devanur N, Lykouris T (2023) Static pricing for multi-unit prophet inequalities. Oper. Res. 72(4):1388–1399.Google Scholar
• Freund D, Banerjee S (2019) Good prophets know when the end is near. Preprint, submitted November 25, https://dx.doi.org/10.2139/ssrn.3479189.Google Scholar
• Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated Online Mechanism Design and Prophet Inequalities, vol. 7 (AAAI, Palo Alto, CA).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
• Jiang J, Ma W, Zhang J (2022a) Degeneracy is ok: Logarithmic regret for network revenue management with indiscrete distributions. Preprint, submitted October 14, https://arxiv.org/abs/2210.07996.Google Scholar
• Jiang J, Ma W, Zhang J (2022b) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Proc. Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1221–1246.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, Talluri K, Topaloglu H (2012) A randomized linear programming method for network revenue management with product-specific no-shows. Transportation Sci. 46(1):90–108.Link, 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
• Lueker GS (1998) Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2):277–305.Crossref, Google Scholar
• Moser L (1956) On a problem of Cayley. Scripta Math. 22:289–292.Google Scholar
• Shen X, Boyd S (2021) Incremental proximal multi-forecast model predictive control. Preprint, submitted November 29, https://arxiv.org/abs/2111.14728.Google Scholar
• Sinclair SR, Vieira Frujeri F, Cheng C-A, Marshall L, Barbalho HDO, Li J, Neville J, Menache I, Swaminathan A (2023) Hindsight learning for MDPs with exogenous inputs. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn. (PMLR, New York), 31877–31914.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.Google Scholar
• Talluri K, Van Ryzin G (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 (2006) The Theory and Practice of Revenue Management, vol. 68 (Springer Science & Business Media, Boston).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