The Competitive Ratio of Threshold Policies for Online Unit-Density Knapsack Problems

References

• Anunrojwong J, Balseiro S, Besbes O (2022) On the robustness of second-price auctions in prior-independent mechanism design. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 151–152.Google Scholar
• Arnosti N, Ma W (2023) Tight guarantees for static threshold policies in the prophet secretary problem. Oper. Res. 71(5):1777–1788.Link, Google Scholar
• Azar Y, Cohen IR, Kamara S, Shepherd B (2013) Tight bounds for online vector bin packing. Proc. 45th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 961–970.Google Scholar
• Correa J, Saona R, Ziliotto B (2021) Prophet secretary through blind strategies. Math. Programming 190(1):483–521.Crossref, Google Scholar
• Cygan M, Jeż Ł, Sgall J (2016) Online knapsack revisited. Theory Comput. Systems 58(1):153–190.Crossref, Google Scholar
• Daneshvaramoli M, Karisani H, Lechowicz A, Sun B, Musco C, Hajiesmaili M (2024) Competitive algorithms for online knapsack with succinct predictions. Preprint, submitted June 26, https://arxiv.org/abs/2406.18752.Google Scholar
• Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Devanur NR, Hayes TP (2009) The AdWords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce (ACM, New York), 71–78.Google Scholar
• Devanur NR, Jain K (2012) Online matching with concave returns. Proc. 44th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 137–144.Google Scholar
• Elmachtoub AN, Shi J (2023) The power of static pricing for reusable resources. Preprint, submitted February 23, https://arxiv.org/abs/2302.11723.Google Scholar
• Feldman M, Gravin N, Lucier B (2014) Combinatorial auctions via posted prices. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 123–135.Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 982–991.Google Scholar
• Goyal V, Udwani R (2023) Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Oper. Res. 71(2):563–580.Link, Google Scholar
• Han X, Kawase Y, Makino K (2015) Randomized algorithms for online knapsack problems. Theoret. Comput. Sci. 562:395–405.Crossref, Google Scholar
• Huang Z, Zhang Q (2020) Online primal dual meets online matching with stochastic rewards: Configuration LP to the rescue. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1153–1164.Google Scholar
• Huang Z, Zhang Q, Zhang Y (2020) AdWords in a panorama. 2020 IEEE 61st Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 1416–1426.Google Scholar
• Huang Z, Tang ZG, Wu X, Zhang Y (2019) Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals. ACM Trans. Algorithms 15(3):1–15.Crossref, Google Scholar
• Hwang D, Jaillet P, Manshadi V (2018) Online resource allocation under partially predictable demand. Preprint, submitted September 30, https://arxiv.org/abs/1810.00447.Google Scholar
• Jiang J, Ma W, Zhang J (2024) Tight guarantees for multiunit prophet inequalities and online stochastic knapsack. Oper. Res. 73(3):1703–1721.Link, Google Scholar
• Kalyanasundaram B, Pruhs K (1993) Online weighted matching. J. Algorithms 14(3):478–488.Crossref, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358.Google Scholar
• Kleywegt AJ, Papastavrou JD (1998) The dynamic and stochastic knapsack problem. Oper. Res. 46(1):17–35.Link, Google Scholar
• Lechowicz A, Sengupta R, Sun B, Kamali S, Hajiesmaili M (2023) Time fairness in online knapsack problems. Preprint, submitted May 22, https://arxiv.org/abs/2305.13293.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
• Marchetti-Spaccamela A, Vercellis C (1995) Stochastic on-line knapsack problems. Math. Programming 68(1–3):73–104.Crossref, Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2005) AdWords and generalized on-line matching. 46th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 264–273.Google Scholar
• Modaresi S, Saure D, Vielma JP (2020) Learning in combinatorial optimization: What and how to explore. Oper. Res. 68(5):1585–1604.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
• Simchi-Levi D, Chen X, Bramel J (2005) The logic of logistics. Theory, Algorithms, and Applications for Logistics and Supply Chain Management (Springer New York, New York).Google Scholar
• Stein C, Truong VA, Wang X (2020) Advance service reservations with heterogeneous customers. Management Sci. 66(7):2929–2950.Link, Google Scholar
• Sun B, Yang L, Hajiesmaili M, Wierman A, Lui JC, Towsley D, Tsang DH (2022) The online knapsack problem with departures. Proc. ACM Measurement Anal. Comput. Systems 6(3):1–32.Crossref, Google Scholar
• Wang S (2023) The power of simple menus in robust selling mechanisms. Preprint, submitted October 26, https://arxiv.org/abs/2310.17392.Google Scholar
• Yao ACC (1977) Probabilistic computations: Toward a unified measure of complexity. 18th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 222–227.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
• Zhou Y, Chakrabarty D, Lukose R (2008) Budget constrained bidding in keyword auctions and online knapsack problems. International Workshop Internet Network Econom. (Springer, Berlin, Heidelberg), 566–576.Crossref, Google Scholar