{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:25:11Z","timestamp":1758273911266,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T00:00:00Z","timestamp":1555459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2021296","1016\/17"],"award-info":[{"award-number":["2021296","1016\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["337122"],"award-info":[{"award-number":["337122"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1444\/14."],"award-info":[{"award-number":["1444\/14."]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["I-1419-118.4\/2017"],"award-info":[{"award-number":["I-1419-118.4\/2017"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00453-019-00569-6","type":"journal-article","created":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T06:02:46Z","timestamp":1555480966000},"page":"3136-3161","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Stable Secretaries"],"prefix":"10.1007","volume":"81","author":[{"given":"Yakov","family":"Babichenko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Emek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ron","family":"Peretz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rann","family":"Smorodinsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,17]]},"reference":[{"key":"569_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, D.J., Bir\u00f3, P., Manlove, D.: \u201cAlmost stable\u201d matchings in the roommates problem. In: Proceedings of Approximation and Online Algorithms, Third International Workshop (WAOA), pp. 1\u201314 (2005)","DOI":"10.1007\/11671411_1"},{"key":"569_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1253\u20131264 (2011)","DOI":"10.1137\/1.9781611973082.95"},{"key":"569_CR3","doi-asserted-by":"crossref","unstructured":"Ashlagi, I., Burq, M., Jaillet, P., Manshadi, V.H.: On matching and thickness in heterogeneous dynamic markets. In: Proceedings of the 2016 ACM Conference on Economics and Computation (EC), p. 765 (2016)","DOI":"10.1145\/2940716.2940758"},{"key":"569_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1086\/689869","volume":"125","author":"I Ashlagi","year":"2016","unstructured":"Ashlagi, I., Kanoria, Y., Leshno, J.D.: Unbalanced random matching markets: the stark effect of competition. J. Polit. Econ. 125, 69\u201398 (2016)","journal-title":"J. Polit. Econ."},{"key":"569_CR5","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 434\u2013443 (2007)"},{"key":"569_CR6","doi-asserted-by":"crossref","unstructured":"Baccara, M., Lee, S., Yariv, L.: Optimal dynamic matching. Available at SSRN: \n                    http:\/\/ssrn.com\/abstract=2641670\n                    \n                  , (2015)","DOI":"10.2139\/ssrn.2641670"},{"issue":"1","key":"569_CR7","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/1360443.1360462","volume":"39","author":"BE Birnbaum","year":"2008","unstructured":"Birnbaum, B.E., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80\u201387 (2008)","journal-title":"SIGACT News"},{"key":"569_CR8","doi-asserted-by":"crossref","unstructured":"Chen, N., Hoefer, M., K\u00fcnnemann, M., Lin, C., Miao, P.: Secretary markets with local information. In: Proceedings of Automata, Languages, and Programming\u201442nd International Colloquium (ICALP), pp. 552\u2013563 (2015)","DOI":"10.1007\/978-3-662-47666-6_44"},{"issue":"4","key":"569_CR9","doi-asserted-by":"publisher","first-page":"2047","DOI":"10.1137\/140996690","volume":"30","author":"CT Cheng","year":"2016","unstructured":"Cheng, C.T.: On the stable matchings that can be reached when the agents go marching in one by one. SIAM J. Discrete Math. 30(4), 2047\u20132063 (2016)","journal-title":"SIAM J. Discrete Math."},{"key":"569_CR10","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 101\u2013107 (2013)","DOI":"10.1137\/1.9781611973105.7"},{"issue":"2","key":"569_CR11","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1145\/2491533.2491557","volume":"44","author":"M Dinitz","year":"2013","unstructured":"Dinitz, M.: Recent advances on the matroid secretary problem. ACM SIGACT News 44(2), 126\u2013142 (2013)","journal-title":"ACM SIGACT News"},{"key":"569_CR12","doi-asserted-by":"crossref","unstructured":"Emek, Y., Kutten, S., Wattenhofer, R.: Online matching: haste makes waste! In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 333\u2013344 (2016)","DOI":"10.1145\/2897518.2897557"},{"issue":"3","key":"569_CR13","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00182-007-0081-6","volume":"36","author":"K Eriksson","year":"2008","unstructured":"Eriksson, K., H\u00e4ggstr\u00f6m, O.: Instability of matchings in decentralized markets with various preference structures. Int. J. Game Theory 36(3), 409\u2013420 (2008)","journal-title":"Int. J. Game Theory"},{"key":"569_CR14","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: A simple o(log log(rank))-competitive algorithm for the matroid secretary problem. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1189\u20131201 (2015)","DOI":"10.1137\/1.9781611973730.79"},{"issue":"3","key":"569_CR15","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1214\/ss\/1177012493","volume":"4","author":"TS Ferguson","year":"1989","unstructured":"Ferguson, T.S.: Who solved the secretary problem? Stat. Sci. 4(3), 282\u2013296 (1989)","journal-title":"Stat. Sci."},{"key":"569_CR16","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"569_CR17","unstructured":"Gardner, M.: New Mathematical Diversions from Scientific American, chapter 3, problem 3. Simon and Schuster, 1966. Reprint of the original column published in February 1960 with additional comments"},{"key":"569_CR18","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 982\u2013991 (2008)"},{"key":"569_CR19","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)"},{"issue":"4","key":"569_CR20","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2956584","volume":"4","author":"A Hassidim","year":"2016","unstructured":"Hassidim, A., Mansour, Y., Vardi, S.: Local computation mechanism design. ACM Trans. Econ. Comput. 4(4), 21:1\u201321:24 (2016)","journal-title":"ACM Trans. Econ. Comput."},{"key":"569_CR21","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing (STOC), pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"569_CR22","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: Proceedings of the 21st Annual European Symposium on Algorithms (ESA), pp. 589\u2013600 (2013)","DOI":"10.1007\/978-3-642-40450-4_50"},{"issue":"2","key":"569_CR23","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255\u2013267 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"569_CR24","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part II, pp. 508\u2013520 (2009)"},{"key":"569_CR25","doi-asserted-by":"crossref","unstructured":"Lachish, O.: O(log log rank) competitive ratio for the matroid secretary problem. In: Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 326\u2013335 (2014)","DOI":"10.1109\/FOCS.2014.42"},{"issue":"2","key":"569_CR26","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF01211824","volume":"8","author":"J Ma","year":"1996","unstructured":"Ma, J.: On randomized matching mechanisms. Econ. Theory 8(2), 377\u2013381 (1996)","journal-title":"Econ. Theory"},{"issue":"12","key":"569_CR27","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1016\/j.ipl.2014.06.013","volume":"114","author":"S Miyazaki","year":"2014","unstructured":"Miyazaki, S.: On the advice complexity of online bipartite matching and online stable marriage. Inf. Process. Lett. 114(12), 714\u2013717 (2014)","journal-title":"Inf. Process. Lett."},{"key":"569_CR28","doi-asserted-by":"crossref","unstructured":"Naor, J., Wajc, D.: Near-optimum online ad allocation for targeted advertising. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC), pp. 131\u2013148 (2015)","DOI":"10.1145\/2764468.2764482"},{"key":"569_CR29","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rosenbaum, W.: Fast distributed almost stable matchings. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pp. 101\u2013108 (2015)","DOI":"10.1145\/2767386.2767424"},{"issue":"4987","key":"569_CR30","doi-asserted-by":"publisher","first-page":"1524","DOI":"10.1126\/science.2274783","volume":"250","author":"AE Roth","year":"1990","unstructured":"Roth, A.E.: New physicians: a natural experiment in market organization. Science 250(4987), 1524\u20131528 (1990)","journal-title":"Science"},{"key":"569_CR31","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Beyond matroids: Secretary problem and prophet inequality with general constraints. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing (STOC), pp. 324\u2013332 (2016)","DOI":"10.1145\/2897518.2897540"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00569-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00569-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00569-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T23:10:23Z","timestamp":1586992223000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00569-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,17]]},"references-count":31,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["569"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00569-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,4,17]]},"assertion":[{"value":"15 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}