Secretaries with Advice

References

• [1] Alabi D, Kalai AT, Ligett K, Musco C, Tzamos C, Vitercik E (2019) Learning to prune: Speeding up repeated computations. Proc. 2019 Conf. Learn. Theory, 30–33.Google Scholar
• [2] Allaart P (2010) A general ‘bang-bang’ principle for predicting the maximum of a random walk. J. Appl. Probab. 47(4):1072–1083.Crossref, Google Scholar
• [3] Antoniadis A, Gouleakis T, Kleer P, Kolev P (2020) Secretary and online matching problems with machine learned advice. Proc. 2020 Conf. Neural Inform. Processing. Systems (NeurIPS, San Diego), 7933–7944.Google Scholar
• [4] Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proc. 25th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1358–1377.Google Scholar
• [5] Balcan M, Dick T, Sandholm T, Vitercik E (2018) Learning to branch. Proc. 35th Internat. Conf. Machine Learn., 353–362.Google Scholar
• [6] Berezovskiy BA, Gnedin AV (1984) The Best Choice Problem (Nauka, Moscow).Google Scholar
• [7] Buchbinder N, Jain K, Singh M (2014) Secretary problems via linear programming. Math. Oper. Res. 39(1):190–206.Link, Google Scholar
• [8] Chan TH, Chen F, Jiang SHC (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. Proc. 26th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1169–1188.Google Scholar
• [9] Correa JR, Cristi A, Epstein B, Soto JA (2020) The two-sided game of googol and sample-based prophet inequalities. Proc. 30th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 2066–2081.Google Scholar
• [10] Correa JR, Dütting P, Fischer FA, Schewior K (2019) Prophet inequalities for I.I.D. random variables from an unknown distribution. Proc. 20th ACM Conf. Econom. Comput. (ACM, New York), 3–17.Google Scholar
• [11] Correa JR, Cristi A, Feuilloley L, Oosterwijk T, Tsigonias-Dimitriadis A (2020) The secretary problem with independent sampling. Proc. 31st ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 2047–2058.Google Scholar
• [12] du Toit J, Peskir G (2009) Selling a stock at the ultimate maximum. Ann. Appl. Probab. 19(3):983–1014.Crossref, Google Scholar
• [13] Dynkin EB (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math. 4:627–629.Google Scholar
• [14] Esfandiari H, Hajiaghayi M, Lucier B, Mitzenmacher M (2020) Prophets, secretaries, and maximizing the probability of choosing the best. Proc. 23rd Internat. Conf. Artificial Intelligence Statist., 3717–3727.Google Scholar
• [15] Ferguson TS (1989) Who solved the secretary problem? Statist. Sci. 4(3):282–289.Crossref, Google Scholar
• [16] Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61(313):35–73.Crossref, Google Scholar
• [17] Gnedin AV (1996) On the full information best-choice problem. J. Appl. Probab. 33(3):678–687.Crossref, Google Scholar
• [18] Hlynka M, Sheahan J (1988) The secretary problem for a random walk. Stochastic Process. Appl. 28(2):317–325.Crossref, Google Scholar
• [19] Indyk P, Vakilian A, Yuan Y (2019) Learning-based low-rank approximations. Proc. 2019 Conf. Neural Inform. Processing Systems (NeurIPS, San Diego), 7400–7410.Google Scholar
• [20] Jain K, Mahdian M, Markakis E, Saberi A, Vazirani VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6):795–824.Crossref, Google Scholar
• [21] Kaplan H, Naori D, Raz D (2020) Competitive analysis with a sample and the secretary problem. Proc. 30th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 2082–2095.Google Scholar
• [22] Kraska T, Beutel A, Chi EH, Dean J, Polyzotis N (2018) The case for learned index structures. Proc. 2018 Internat. Conf. Management Data, 489–504.Google Scholar
• [23] Lattanzi S, Lavastida T, Moseley B, Vassilvitskii S (2020) Online scheduling via learned weights. Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1859–1877.Google Scholar
• [24] Lykouris T, Vassilvitskii S (2018) Competitive caching with machine learned advice. Proc. 35th Internat. Conf. Machine Learn., 3302–3311.Google Scholar
• [25] Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. Proc. 43rd ACM Sympos. Theory Comput. (ACM, New York), 597–606.Google Scholar
• [26] Medina AM, Vassilvitskii S (2017) Revenue optimization with approximate bid predictions. Proc. 2017 Conf. Neural Inform. Processing Systems (NeurIPS, San Diego), 1858–1866.Google Scholar
• [27] Mehta A, Saberi AU, Vazirani U, Vazirani VV (2007) Adwords and generalized online matching. J. ACM 54(5):22–40.Crossref, Google Scholar
• [28] Mitzenmacher M (2018) A model for learned bloom filters and optimizing by sandwiching. Proc. 2018 Conf. Neural Inform. Processing Systems (NeurIPS, San Diego), 462–471.Google Scholar
• [29] Mitzenmacher M (2021) Queues with small advice. Proc. 2021 SIAM Conf. Appl. Comput. Discrete Algorithms (SIAM, Philadelphia), 1–12.Google Scholar
• [30] Purohit M, Svitkina Z, Kumar R (2018) Improving online algorithms via ML predictions. Proc. 2018 Conf. Neural Inform. Processing Systems (NeurIPS, San Diego), 9684–9693.Google Scholar
• [31] Rohatgi D (2020) Near-optimal bounds for online caching with machine learned advice. Proc. 30th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1834–1845.Google Scholar
• [32] Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. Proc. 11th Innovations Theoret. Comput. Sci. Conf., 60:1–60:10.Google Scholar
• [33] Samuels S (1982) Exact solutions for the full information best choice problem. Purdue University Statistics Mimeo Series 81–87, Purdue University, West Lafayette, IN.Google Scholar
• [34] Yam SCP, Yung SP, Zhou W (2009) Two rationales behind the ‘buy-and-hold or sell-at-once’ strategy. J. Appl. Probab. 46(3):651–668.Crossref, Google Scholar