{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:36:20Z","timestamp":1787340980353,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100011643","name":"Blavatnik Family Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100011643","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1595-19"],"award-info":[{"award-number":["1595-19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1156\/23"],"award-info":[{"award-number":["1156\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model. We study the classical secretary problem in our new models. In the worst-case model we present a simple online algorithm with optimal competitive-ratio for any sample size. In the random-order model, we also give a simple online algorithm with an almost tight competitive-ratio for small sample sizes. Interestingly, we prove that for a large enough sample, no algorithm can be simultaneously optimal in both the worst-case and random-order models.<\/jats:p>","DOI":"10.1137\/24m1650223","type":"journal-article","created":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T09:00:33Z","timestamp":1764925233000},"page":"1489-1513","source":"Crossref","is-referenced-by-count":0,"title":["Competitive Analysis with a Sample and the Secretary Problem"],"prefix":"10.1137","volume":"54","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[{"name":"The Blavatnik School of Computer Science and AI, Tel Aviv University, Tel Aviv, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8466-3546","authenticated-orcid":true,"given":"David","family":"Naori","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Technion, Haifa, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danny","family":"Raz","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Technion, Haifa, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"ref1","first-page":"13852","volume-title":"Advances in Neural Information Processing Systems (NeurIPS)","author":"Argue C.","year":"2022"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"P. Azar, R. Kleinberg, and M. Weinberg, Prophet inequalities with limited information, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014, pp. 1358\u20131377, https:\/\/doi.org\/10.1137\/1.9781611973402.100.","DOI":"10.1137\/1.9781611973402.100"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"ref4","unstructured":"M. Babaioff, N. Immorlica, and R. Kleinberg, Matroids, secretary problems, and online mechanisms, in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, pp. 434\u2013443."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0604"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2023.1363"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"J. Correa, A. Cristi, L. Feuilloley, T. Oosterwijk, and A. Tsigonias-Dimitriadis, The secretary problem with independent sampling, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, pp. 2047\u20132058, https:\/\/doi.org\/10.1137\/1.9781611976465.122.","DOI":"10.1137\/1.9781611976465.122"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"J. Correa, P. D\u00fctting, F. Fischer, and K. Schewior, Prophet inequalities for i.i.i. random variables from an unknown distribution, in Proceedings of the 2019 ACM Conference on Economics and Computation (EC), 2019, pp. 3\u201317.","DOI":"10.1145\/3328526.3329627"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3331033.3331039"},{"key":"ref10","first-page":"627","volume":"4","author":"Dynkin E.","year":"1963","journal-title":"Soviet Math. Dokl."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1966.10502008"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_43"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993861"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"H. Kaplan, D. Naori, and D. Raz, Competitive analysis with a sample and the secretary problem, in Proceedings of the 2020 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020, pp. 2082\u20132095, https:\/\/doi.org\/10.1137\/1.9781611975994.128.","DOI":"10.1137\/1.9781611975994.128"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"H. Kaplan, D. Naori, and D. Raz, Online weighted matching with a sample, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022, pp. 1247\u20131272, https:\/\/doi.org\/10.1137\/1.9781611977073.52.","DOI":"10.1137\/1.9781611977073.52"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(86)90095-3"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"T. Kesselheim, R. Kleinberg, and R. Niazadeh, Secretary problems with non-uniform arrival order, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 879\u2013888.","DOI":"10.1145\/2746539.2746602"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"T. Kesselheim, K. Radke, A. T\u00f6nnis, and B. V\u00f6cking, An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions, in Proceedings of the 21st Annual European Symposium on Algorithms (ESA), 2013, pp. 589\u2013600.","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"ref19","unstructured":"R. Kleinberg, A multiple-choice secretary algorithm with applications to online auctions, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 630\u2013631."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.2307\/2985407"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4259"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"D. Naori and D. Raz, Online placement of virtual machines with prior data, in IEEE Conference on Computer Communications (INFOCOM), 2020, pp. 2539\u20132548.","DOI":"10.1109\/INFOCOM41043.2020.9155339"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/3232535"},{"key":"ref25","unstructured":"A. Rubinstein, J. Z. Wang, and S. M. Weinberg, Optimal single-choice prophet inequalities from samples, in 11th Innovations in Theoretical Computer Science Conference (ITCS), 2020, 60."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-022-00916-4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1650223","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:59:19Z","timestamp":1787338759000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1650223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,5]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1137\/24M1650223"],"URL":"https:\/\/doi.org\/10.1137\/24m1650223","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,5]]}}}