The Secretary Problem with Predictions

References

• [1] Albers S, Ladewig L (2019) New results for the k-secretary problem. Lu P, Zhang G, eds. Proc. 30th Internat. Sympos. on Algorithms and Comput. (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 18:1–18:19.Google Scholar
• [2] Antoniadis A, Gouleakis T, Kleer P, Kolev P (2020) Secretary and online matching problems with machine learned advice. Larochelle H, Ranzato M, Hadsell R, Balcan M, Lin H, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, NY), 7933–7944.Google Scholar
• [3] Antoniadis A, Coester C, Eliás M, Polak A, Simon B (2020) Online metric algorithms with untrusted predictions. Daumé III H, Singh A, eds. Proc. 37th Internat. Conf. on Machine Learn. (Proceedings of Machine Learning Research, New York), 345–355.Google Scholar
• [4] Azar Y, Chiplunkar A, Kaplan H (2018) Prophet secretary: Surpassing the 1 − 1/e barrier. Tardos E, Elkind E, Vohra R, eds. Proc. ACM Conf. on Econom. and Comput. (Association for Computing Machinery, New York), 303–318.Google Scholar
• [5] Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007) A knapsack secretary problem with applications. Charikar M, Jansen K, Reingold O, Rolim JDP, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer-Verlag, Berlin Heidelberg), 16–28.Google Scholar
• [6] Balcan M, Dick T, Sandholm T, Vitercik E (2018) Learning to branch. Dy JG, Krause A, eds. Proc. 35th Internat. Conf. on Machine Learn. (Proceedings of Machine Learning Research, New York), 353–362.Google Scholar
• [7] Bamas É, Maggiori A, Svensson O (2020) The primal-dual method for learning augmented algorithms. Larochelle H, Ranzato M, Hadsell R, Balcan M, Lin H, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, NY), 20083–20094.Google Scholar
• [8] Bamas É, Maggiori A, Rohwedder L, Svensson O (2020) Learning augmented energy minimization via speed scaling. Larochelle H, Ranzato M, Hadsell R, Balcan M, Lin H, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, NY), 15350–15359.Google Scholar
• [9] Bradac D, Gupta A, Singla S, Zuzic G (2020) Robust algorithms for the secretary problem. Vidick T, ed. Proc. 11th Innovations in Theoretical Comput. Sci. Conf. (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 32:1–32:26.Google Scholar
• [10] Bruss FT (1984) A unified approach to a class of best choice problems with an unknown number of options. Ann. Probability 12(3):882–889.Crossref, Google Scholar
• [11] Buchbinder N, Jain K, Singh M (2014) Secretary problems via linear programming. Math. Oper. Res. 39(1):190–206.Link, Google Scholar
• [12] Campbell G, Samuels SM (1981) Choosing the best of the current crop. Adv. Appl. Probability 13(3):510–532.Crossref, Google Scholar
• [13] Chan TH, Chen F, Jiang SH (2015) Revealing optimal thresholds for generalized secretary problem via continuous LP: Impacts on online K-item auction and bipartite K-matching with random arrival order. Indyk P, ed. Proc. 26th Annual ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1169–1188.Google Scholar
• [14] Chao MT, Strawderman WE (1972) Negative moments of positive random variables. J. Amer. Statist. Assoc. 67(338):429–431.Crossref, Google Scholar
• [15] Correa JR, Saona R, Ziliotto B (2019) Prophet secretary through blind strategies. Chan TM, ed. Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 1946–1961.Google Scholar
• [16] Correa JR, Saona R, Ziliotto B (2021c) Prophet secretary through blind strategies. Math. Program. 190(1):483–521.Crossref, Google Scholar
• [17] Correa JR, Cristi A, Feuilloley L, Oosterwijk T, Tsigonias-Dimitriadis A (2021) The secretary problem with independent sampling. Marx D, ed. Proc. ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2047–2058.Google Scholar
• [18] Correa JR, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2021) Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4):1452–1478.Link, Google Scholar
• [19] Dütting P, Lattanzi S, Leme RP, Vassilvitskii S (2021) Secretaries with advice. Biró P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. on Econom. and Comput. (Association for Computing Machinery, New York), 409–429.Google Scholar
• [20] Dynkin EB (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math. Doklady (4):627–629.Google Scholar
• [21] Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Czumaj A, ed. Proc. 29th Annual ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 700–714.Google Scholar
• [22] Esfandiari H, Hajiaghayi M, Liaghat V, Monemizadeh M (2017) Prophet secretary. SIAM J. Discrete Math. 31(3):1685–1701.Crossref, Google Scholar
• [23] Feldman M, Naor J, Schwartz R (2011) Improved competitive ratios for submodular secretary problems. Goldberg LA, Jansen K, Ravi R, Rolim JDP, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer-Verlag, Berlin Heidelberg), 218–229.Google Scholar
• [24] Gardner M (1960) Mathematical games. Sci. Amer. 202(3):172–186.Crossref, Google Scholar
• [25] Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61:35–73.Crossref, Google Scholar
• [26] Gollapudi S, Panigrahi D (2019) Online algorithms for rent-or-buy with expert advice. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. on Machine Learn. (Proceedings of Machine Learning Research, New York), 2319–2327.Google Scholar
• [27] Kaplan H, Naori D, Raz D (2020) Competitive analysis with a sample and the secretary problem. Chawla S, ed. Proc. ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2082–2095.Google Scholar
• [28] Kesselheim T, Molinaro M (2020) Knapsack secretary with bursty adversary. Czumaj A, Dawar A, Merelli E, eds. Proc. 47th Internat. Colloquium on Automata, Languages, and Programming (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 72:1–72:15.Google Scholar
• [29] Kleinberg RD (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. 16th Annual ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 630–631.Google Scholar
• [30] Lattanzi S, Lavastida T, Moseley B, Vassilvitskii S (2020) Online scheduling via learned weights. Chawla S, ed. Proc. ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1859–1877.Google Scholar
• [31] Lindley DV (1961) Dynamic programming and decision theory. J. Royal Statist. Soc. Ser. C. Appl. Statist. 10(1):39–51.Google Scholar
• [32] Lykouris T, Vassilvitskii S (2018) Competitive caching with machine learned advice. Dy JG, Krause A, eds. Proc. 35th Internat. Conf. on Machine Learn. (Proceedings of Machine Learning Research, New York), 3302–3311.Google Scholar
• [33] Mitzenmacher M (2018) A model for learned bloom filters and optimizing by sandwiching. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, NY), 462–471.Google Scholar
• [34] Purohit M, Svitkina Z, Kumar R (2018) Improving online algorithms via ML predictions. Bengio S, Wal-lach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, NY), 9684–9693.Google Scholar
• [35] Rohatgi D (2020) Near-optimal bounds for online caching with machine learned advice. Chawla S, ed. Proc. ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1834–1845.Google Scholar
• [36] Sabato S, Hess T (2017) Interactive algorithms: Pool, stream and precognitive stream. J. Machine Learn. Res. 18:229:1–229:39.Google Scholar
• [37] Wei A (2020) Better and simpler learning-augmented online caching. Byrka J, Meka R, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 60:1–60:17.Google Scholar
• [38] Wei A, Zhang F (2020) Optimal robustness-consistency trade-offs for learning-augmented online algorithms. Larochelle H, Ranzato M, Hadsell R, Balcan M, Lin H, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, NY), 8042–8053.Google Scholar