{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T09:03:22Z","timestamp":1764925402115,"version":"3.46.0"},"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","1156\/23"],"award-info":[{"award-number":["1595-19","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]]},"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."}]},{"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."}]},{"given":"Danny","family":"Raz","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Technion, Haifa, Israel."}]}],"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","deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T09:00:36Z","timestamp":1764925236000},"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]]}}}