Infrequent Resolving Algorithm for Online Linear Programming

References

• [1] 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
• [2] Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• [3] Balseiro S, Lu H, Mirrokni V (2020) Dual mirror descent for online allocation problems. Proc. 37th Internat. Conf. Machine Learn., vol. 119 (PMLR, New York), 613–628.Google Scholar
• [4] Balseiro SR, Lu H, Mirrokni V (2023a) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• [5] Balseiro SR, Lu H, Mirrokni V, Sivan B (2023b) Analysis of dual-based PID controllers through convolutional mirror descent. Preprint, submitted February 12, https://arxiv.org/abs/2202.06152.Google Scholar
• [6] Banerjee S, Freund D (2024) Good prophets know when the end is near. Management Sci. 71(6):4877–4894.Link, Google Scholar
• [7] Besbes O, Zeevi A (2012) Blind network revenue management. Oper. Res. 60(6):1537–1550.Link, Google Scholar
• [8] Besbes O, Kanoria Y, Kumar A (2025) Dynamic resource allocation: Algorithmic design principles and spectrum of achievable performances. Oper. Res. 73(3):1273–1288.Link, Google Scholar
• [9] Borodin A, El-Yaniv R (2005) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• [10] Bray RL (2025) Logarithmic regret in multisecretary and online linear programs with continuous valuations. Oper. Res. 73(4):2188–2203.Link, Google Scholar
• [11] Buchbinder N, Naor J (2009a) Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2):270–286.Link, Google Scholar
• [12] Buchbinder N, Naor J (2009b) The design of competitive online algorithms via a primal–dual approach. Foundations Trends Theoret. Comput. Sci. 3(2–3):93–263.Crossref, Google Scholar
• [13] Buchbinder N, Jain K, Naor J (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Arge L, Hoffmann M, Welzl E, eds. Algorithms – ESA 2007, Lecture Notes in Computer Science, vol. 4698 (Springer, Berlin, Heidelberg), 253–264.Google Scholar
• [14] 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
• [15] Chen Y, Wang W (2025) Beyond non-degeneracy: Revisiting certainty equivalent heuristic for online linear programming. Preprint, submitted January 3, https://arxiv.org/abs/2501.01716.Google Scholar
• [16] Chen G, Li X, Ye Y (2024) An improved analysis of LP-based control for revenue management. Oper. Res. 72(3):1124–1138.Link, Google Scholar
• [17] Cooper WL (2002) Asymptotic behavior of an allocation policy for revenue management. Oper. Res. 50(4):720–727.Link, Google Scholar
• [18] Ferreira KJ, Simchi-Levi D, Wang H (2018) Online network revenue management using Thompson sampling. Oper. Res. 66(6):1586–1602.Link, Google Scholar
• [19] Gallego G, Van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Sci. 40(8):999–1020.Link, Google Scholar
• [20] Gao W, Ge D, Sun C, Ye Y (2023) Solving linear programs with fast online learning algorithms. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. ICML’23: Proc. 40th Internat. Conf. Machine Learn. (JMLR, New York), 10649–10675.Google Scholar
• [21] Gao Z, Han Y, Ren Z, Zhou Z (2019) Batched multi-armed bandits problem. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, eds. Proc. 33rd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 503–513.Google Scholar
• [22] Gao W, Sun C, Xue C, Ye Y (2024) Decoupling learning and decision-making: Breaking the O(T) barrier in online resource allocation with first-order methods. Proc. 41st Internat. Conf. Machine Learn., vol. 235 (PMLR, New York), 14859–14883.Google Scholar
• [23] Gupta V (2024) Greedy algorithm for multiway matching with bounded regret. Oper. Res. 72(3):1139–1155.Link, Google Scholar
• [24] Gupta A, Molinaro M (2014) How experts can solve LPs online. Schulz AS, Wagner D, eds. Algorithms - ESA 2014, Lecture Notes in Computer Science, vol. 8737 (Springer, Berlin, Heidelberg), 517–529.Google Scholar
• [25] Han Y, Zhou Z, Zhou Z, Blanchet J, Glynn PW, Ye Y (2020) Sequential batch learning in finite-action linear contextual bandits. Preprint, submitted April 14, https://arxiv.org/abs/2004.06321.Google Scholar
• [26] Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optim. 2(3–4):157–325.Crossref, Google Scholar
• [27] He S, Wei Y, Xu J, Yu SH (2025) Online resource allocation without re-solving: The effectiveness of primal-dual policies. Preprint, submitted February 24, https://doi.org/10.2139/ssrn.5133857.Google Scholar
• [28] Jasin S (2015) Performance of an LP-based control for revenue management with unknown demand parameters. Oper. Res. 63(4):909–915.Link, Google Scholar
• [29] 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
• [30] 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
• [31] 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
• [32] Jiang J, Li X, Zhang J (2025a) Online stochastic optimization with Wasserstein based non-stationarity. Management Sci. 71(11):9104–9122.Link, Google Scholar
• [33] Jiang J, Ma W, Zhang J (2025b) Degeneracy is OK: Logarithmic regret for network revenue management with indiscrete distributions. Oper. Res. 73(6):3405–3420.Link, Google Scholar
• [34] Kesselheim T, Tönnis A, Radke K, Vöcking B (2014) Primal beats dual on online packing LPs in the random-order model. STOC’14: Proc. 46th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 303–312.Google Scholar
• [35] Li X, Ye Y (2022) Online linear programming: Dual convergence, new algorithms, and regret bounds. Oper. Res. 70(5):2948–2966.Link, Google Scholar
• [36] Li X, Sun C, Ye Y (2020) Simple and fast algorithm for binary integer and online linear programming. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. NIPS’20: Proc. 34th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 9412–9421.Google Scholar
• [37] Ma W, Cao Y, Tsang DH, Xia D (2025) Optimal regularized online allocation by adaptive re-solving. Oper. Res. 73(4):2079–2096.Link, Google Scholar
• [38] Mangasarian OL, Shiau TH (1987) Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. SIAM J. Control Optim. 25(3):583–595.Crossref, Google Scholar
• [39] Mehta A, Saberi A, Vazirani U, Vazirani V (2005) AdWords and generalized online matching. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 264–273.Google Scholar
• [40] Meyn S, Tweedie R (2012) Markov Chains and Stochastic Stability (Springer-Verlag, London).Google Scholar
• [41] Mittelmann H (2024) LPopt benchmark (find optimal basic solution). Accessed December 28, 2024, https://plato.asu.edu/ftp/lpopt.html.Google Scholar
• [42] Molinaro M, Ravi R (2014) The geometry of online packing linear programs. Math. Oper. Res. 39(1):46–59.Link, Google Scholar
• [43] Perchet V, Rigollet P, Chassang S, Snowberg E (2016) Batched bandit problems. Ann. Statist. 44(2):660–681.Crossref, Google Scholar
• [44] Reiman M, 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
• [45] Ren Z, Zhou Z (2024) Dynamic batch learning in high-dimensional sparse linear contextual bandits. Management Sci. 70(2):1315–1342.Link, Google Scholar
• [46] Ruan Y, Yang J, Zhou Y (2021) Linear bandits with limited adaptivity and learning distributional optimal design. STOC 2021: Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 74–87.Google Scholar
• [47] Statista (2024) Most popular travel and tourism websites worldwide from April 2022 to January 2024, based on average monthly visits (in millions). Accessed December 28, 2024, https://www.statista.com/statistics/1388573/top-travel-tourism-websites-by-monthly-visits/.Google Scholar
• [48] Sun R, Wang X, Zhou Z (2020) Near-optimal primal-dual algorithms for quantity-based network revenue management. Preprint, submitted November 12, https://arxiv.org/abs/2011.06327.Google Scholar
• [49] Talluri K, Van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Management Sci. 44(11):1577–1593.Link, Google Scholar
• [50] Vera A, Banerjee S (2020) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar
• [51] 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
• [52] Wei Y, Xu J, Yu SH (2023) Constant regret primal-dual policy for multi-way dynamic matching. Preprint, submitted February 14, https://doi.org/10.2139/ssrn.4357216.Google Scholar
• [53] Xie Y, Ma W, Xin L (2025) The benefits of delay to online decision making. Management Sci. 72(4):2826–2841.Link, Google Scholar
• [54] Zhang J (2026) Online resource allocation with continuous random consumption: Regret under degeneracy. Preprint, submitted July 2, https://arxiv.org/abs/2607.02196.Google Scholar
• [55] 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