Good Prophets Know When the End Is Near

References

• Agarwal D, Ghosh S, Wei K, You S (2014) Budget pacing for targeted online advertisements at LinkedIn. Macskassy SA, Perlich C, Leskovec J, Wang W, Ghani R, eds. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1613–1619.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
• Ahani N, Gölz P, Procaccia AD, Teytelboym A, Trapp AC (2024) Dynamic placement in refugee resettlement. Comm. ACM 67(5):99–106.Crossref, Google Scholar
• Alaei S, Hajiaghayi M, Liaghat V (2013) The online stochastic generalized assignment problem. Raghavendra P, Raskhodnikova S, Jansen K, Rolim JDP, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 11–25.Crossref, Google Scholar
• Albers S, Mitzenmacher M (2000) Average-case analyses of first fit and random fit bin packing. Random Structures Algorithms 16(3):240–259.Crossref, Google Scholar
• Alijani R, Banerjee S, Gollapudi S, Munagala K, Wang K (2020) Predict and match: Prophet inequalities with uncertain supply. Proc. ACM Measurement Anal. Comput. Systems 4(1):1–23.Crossref, 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
• Balseiro SR, Xia S (2022) Uniformly bounded regret in dynamic fair allocation. Preprint, submitted May 25, https://arxiv.org/abs/2205.12447.Google Scholar
• Bansak K, Paulson E (2024) Outcome-driven dynamic refugee assignment with allocation balancing. Oper. Res., ePub ahead of print March 25, https://doi.org/10.1287/opre.2022.0445.Link, Google Scholar
• Berry AC (1941) The accuracy of the gaussian approximation to the sum of independent variates. Trans. Amer. Math. Soc. 49(1):122–136.Crossref, Google Scholar
• Bertsekas DP (2011) Dynamic Programming and Optimal Control, 3rd ed., vol. ii (Athena Scientific, Belmont, MA).Google Scholar
• Bray RL (2019) Does the multisecretary problem always have bounded regret? Preprint, submitted December 16, https://arxiv.org/abs/1912.08917.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
• 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
• Coffman EG Jr, Courcoubetis C, Garey M, Johnson DS, McGeoch LA, Shor PW, Weber RR, Yannakakis M (1991) Fundamental discrepancies between average-case analyses under discrete and continuous distributions: A bin packing case study. Koutsougeras C, Vitter JS, eds. Proc. 23rd Annual ACM Sympos. Theory Comput. (ACM, New York), 230–240.Google Scholar
• Courcoubetis C, Weber R (1986) Necessary and sufficient conditions for stability of a bin-packing system. J. Appl. Probab. 23(4):989–999.Crossref, Google Scholar
• Csirik J, Johnson DS, Kenyon C, Orlin JB, Shor PW, Weber RR (2006) On the sum-of-squares algorithm for bin packing. J. ACM 53(1):1–65.Crossref, Google Scholar
• Dal Pozzolo A, Caelen O, Johnson RA, Bontempi G (2015) Calibrating probability with undersampling for unbalanced classification. Engelbrecht A, ed. 2015 IEEE Sympos. Ser. Comput. Intelligence (IEEE, Piscataway, NJ), 159–166.Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2019) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1):1–41.Crossref, Google Scholar
• Düetting P, Feldman M, Kesselheim T, Lucier B (2020) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. SIAM J. Comput. 49(3):540–582.Google Scholar
• Elliott J (2020) The 7 best credit card processing companies of 2020. Investopedia. Accessed September 15, 2024, https://investopedia.com/best-credit-card-processing-companies-5080522.Google Scholar
• Esseen CG (1956) A moment inequality with an application to the central limit theorem. Scand. Actuar. J. 1956(2):160–170.Crossref, Google Scholar
• Freund D, Zhao J (2022) Overbooking with bounded loss. Math. Oper. Res. 48(3):1344–1363.Link, Google Scholar
• Gaitonde J, Li Y, Light B, Lucier B, Slivkins A (2022) Budget pacing in repeated auctions: Regret and efficiency without convergence. Preprint, submitted May 18, https://arxiv.org/abs/2205.08674.Google Scholar
• Gupta V, Radovanović A (2020) Interior-point-based online stochastic bin packing. Oper. Res. 68(5):1474–1492.Link, Google Scholar
• Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Howe A, Holte RC, eds. AAAI’07 Proc. 22nd Natl. Conf. Artificial Intelligence, vol. 1 (AAAI, Washington, DC), 58–65.Google Scholar
• Hoeffding W (1994) Probability inequalities for sums of bounded random variables. Fisher NI, Sen PK, eds. The Collected Works of Wassily Hoeffding. Springer Series in Statistics (Springer, Berlin), 409–426.Crossref, 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
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Buchsbaum A, ed. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 630–631.Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Pitassi T, ed. Proc. 44th Annual ACM Sympos. Theory Comput. (ACM, New York), 123–136.Google Scholar
• Liu S, Li X (2021) Online bin packing with known T. Preprint, submitted December 6, https://arxiv.org/abs/2112.03200.Google Scholar
• 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
• Rhee WT, Talagrand M (1993) Online bin packing with items of random size. Math. Oper. Res. 18(2):438–445.Link, Google Scholar
• Samuel-Cahn E (1996) Optimal stopping with random horizon with application to the full-information best-choice problem with random freeze. J. Amer. Statist. Assoc. 91(433):357–364.Crossref, Google Scholar
• Shevtsova I (2011) On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands. Preprint, submitted November 28, https://arxiv.org/abs/1111.6554.Google Scholar
• Shor PW (1986) The average-case analysis of some on-line algorithms for bin packing. Combinatorica 6(2):179–200.Crossref, Google Scholar
• Shor PW (1991) How to pack better than best fit: Tight bounds for average-case online bin packing. Sipser M, ed. Proc. 32nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 752–759.Google Scholar
• Sinclair SR, Frujeri FV, Cheng CA, Marshall L, Barbalho HDO, Li J, Neville J, Menache I, Swaminathan A (2023) Hindsight learning for MDPs with exogenous inputs. Engelhardt B, Brunskill E, Cho K, eds. Proc. 40th Internat. Conf. Machine Learn. (PMLR, New York), 31877–31914.Google Scholar
• Square (2020) Payments processor’s fee. (August 14), https://squareup.com/us/en/townsquare/credit-card-processing-fees-and-rates.Google Scholar
• Sun R, Wang X, Zhou Z (2020) Near-optimal primal-dual algorithms for quantity-based network revenue management. Preprint, submitted November 11, http://dx.doi.org/10.2139/ssrn.3728397.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
• 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