{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T15:29:57Z","timestamp":1748618997603,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the paper, the generalisation of the well-known \u201csecretary problem\u201d is considered. The aim of the paper is to give a generalised model in such a way that the chosen set of the possible best <jats:italic>k<\/jats:italic> elements have to be independent of all previously rejected elements. The independence is formulated using the theory of greedoids and in their special cases\u2014matroids and antimatroids. Examples of some special cases of greedoids (uniform, graphical matroids and binary trees) are considered. Applications in cloud computing are discussed.<\/jats:p>","DOI":"10.1007\/s43069-021-00092-x","type":"journal-article","created":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T19:02:43Z","timestamp":1637175763000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Secretary Problem: Graphs, Matroids and Greedoids"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6997-3658","authenticated-orcid":false,"given":"Wojciech","family":"Kordecki","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,17]]},"reference":[{"key":"92_CR1","doi-asserted-by":"publisher","unstructured":"Babaioff M, Immorlica N, Kempe D, Kleinberg R (2008) Online auctions and generalized secretary problems. SIGecom Exch\u00a07 (2): 7:1\u20137:11. ISSN 1551-9031. 10.1145\/1399589.1399596. https:\/\/doi.org\/10.1145\/1399589.1399596","DOI":"10.1145\/1399589.1399596"},{"key":"92_CR2","doi-asserted-by":"crossref","unstructured":"Babaioff M, Immorlica N, Kleinberg R (2018) Matroid secretary problems. J ACM\u00a065 (6): 35:1\u201335:26","DOI":"10.1145\/3212512"},{"key":"92_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s B (2001) Random Graphs. Academic Press, London"},{"issue":"6","key":"92_CR4","first-page":"499","volume":"13","author":"H Dai","year":"2019","unstructured":"Dai H, Yang Y, Yin JS, Jiang H, Li C (2019) Improved greedy strategy for cloud computing resources scheduling. ICIC Express Lett 13(6):499\u2013504.\u00a0http:\/\/www.icicel.org\/ell\/contents\/2019\/6\/el-13-06-09.pdf","journal-title":"ICIC Express Lett"},{"key":"92_CR5","unstructured":"Dai Y-S Yang B, Dongarra J, Zhang G (2009) Cloud service reliability: Modeling and analysis. In 15th IEEE Pacific Rim Intern Symp Depend Comput.\u00a0http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.214.143&rep=rep1&type=pdf"},{"key":"92_CR6","first-page":"627","volume":"4","author":"EB Dynkin","year":"1963","unstructured":"Dynkin EB (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math Dokl 4: 627\u20136290","journal-title":"Soviet Math. Dokl."},{"key":"92_CR7","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s P, R\u00e9nyi A (1960) On the evolution of random graphs. Publications of the Math Inst Hungarian Acad Sci 5: 17\u201361","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"issue":"3","key":"92_CR8","first-page":"282","volume":"4","author":"TS Ferguson","year":"1989","unstructured":"Ferguson TS (1989) Who solved the secretary problem? Stat Sci 4 (3): 282\u2013289","journal-title":"Statistical Science"},{"issue":"4","key":"92_CR9","first-page":"429","volume":"43","author":"B Garrod","year":"2013","unstructured":"Garrod B, Morris R (2013) The secretary problem on an unknown poset. RANSA 43 (4): 429\u2013451","journal-title":"RANSA"},{"key":"92_CR10","doi-asserted-by":"crossref","unstructured":"Girdhar Y, Dudek G (2009) Optimal online data sampling or how to hire the best secretaries. In Canadian Conf Comp Robot Vision\u00a0292\u2013298","DOI":"10.1109\/CRV.2009.30"},{"key":"92_CR11","doi-asserted-by":"crossref","unstructured":"Goecke O, Korte B, Lov\u00e1s L (1989) Examples and algorithmic properties of greedoids. In B.\u00a0Simeone, editor, Combinatorial optimization, volume 1403 of Lecture Notes in Mathematics, pages 113\u2013161. Springer","DOI":"10.1007\/BFb0083463"},{"key":"92_CR12","doi-asserted-by":"crossref","unstructured":"Hajiaghayi MT, Kleinberg R, Parkes DC (2004) Adaptive limited-supply online auctions. In EC\u201904:Proceedings of the 5th ACM Conference on Electronic Commerce, pages 71\u201380, New York,\u00a0ACM Press","DOI":"10.1145\/988772.988784"},{"key":"92_CR13","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S Janson","year":"2000","unstructured":"Janson S, \u0141uczak T, Ruci\u0144ski A (2000) Random Graphs. Wiley, New York"},{"key":"92_CR14","unstructured":"Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, SODA \u201905, pages 630\u2013631, Philadelphia, PA, USA. Soc Industrial Appl Math. ISBN 0-89871-585-7.\u00a0\u00a0http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070519"},{"key":"92_CR15","volume-title":"The Structure of Long-term Memory: A Connectivity Model of Semantic Processing","author":"W Klimesch","year":"1994","unstructured":"Klimesch W (1994) The Structure of Long-term Memory: A Connectivity Model of Semantic Processing. Lawrence Erlbaum Associates Inc, Publishers"},{"issue":"3","key":"92_CR16","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF02579192","volume":"3\u20134","author":"B Korte","year":"1983","unstructured":"Korte B, Lov\u00e1s L (1983) Structural properties of greedoids. Combinatorica 3\u20134 (3): 359\u2013374","journal-title":"Combinatorica"},{"key":"92_CR17","doi-asserted-by":"crossref","unstructured":"Korte B, Vygen J (2012) Combinatorial Optimization, volume 21 of Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg, 5 edition","DOI":"10.1007\/978-3-642-24488-9"},{"key":"92_CR18","doi-asserted-by":"crossref","unstructured":"Korte B, Lov\u00e1sz L, Schrader R (1991) Greedoids, volume 4 of Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg","DOI":"10.1007\/978-3-642-58191-5"},{"key":"92_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0012-365X(97)00091-5","volume":"184","author":"M Morayne","year":"1998","unstructured":"Morayne M (1998) Partial order analogue of the secretary problem: the binary tree case. Discrete Math 184: 165\u2013181","journal-title":"Discrete Math."},{"key":"92_CR20","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001","volume-title":"Matroid Theory","author":"JG Oxley","year":"2011","unstructured":"Oxley JG (2011) Matroid Theory. Oxford University Press, Oxford, 2 edition","edition":"2"},{"issue":"1","key":"92_CR21","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/110852061","volume":"42","author":"JA Soto","year":"2013","unstructured":"Soto JA (2013) Matroid secretary problem in the random-assignment model. SIAM J Comput 42 (1): 178\u2013211","journal-title":"SIAM J. Comput."},{"key":"92_CR22","doi-asserted-by":"crossref","unstructured":"Soto JA, Turkieltaub A, Verdugo V (2018) Algorithms for the ordinal matroid secretary problem. In SODA \u201918 Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 715\u2013734, Philadelphia, USA. Soc Industrial Appl Math","DOI":"10.1137\/1.9781611975031.47"},{"key":"92_CR23","doi-asserted-by":"crossref","unstructured":"van der Hofstad R (2016) Random Graphs and Complex Networks: Volume 1. Cambridge University Press, USA, 1st edition.\u00a0ISBN 110717287X","DOI":"10.1017\/9781316779422"},{"key":"92_CR24","volume-title":"Matroid Theory","author":"DJA Welsh","year":"1976","unstructured":"Welsh DJA\u00a0(1976)\u00a0Matroid Theory. Academic Press, London"},{"key":"92_CR25","unstructured":"Wilson\u00a0RJ (2010)\u00a0Introduction to Graph Theory. Prentice Hall, 5 edition"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-021-00092-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-021-00092-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-021-00092-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T06:22:19Z","timestamp":1640586139000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-021-00092-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,17]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["92"],"URL":"https:\/\/doi.org\/10.1007\/s43069-021-00092-x","relation":{},"ISSN":["2662-2556"],"issn-type":[{"type":"electronic","value":"2662-2556"}],"subject":[],"published":{"date-parts":[[2021,11,17]]},"assertion":[{"value":"29 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares that he has no conflicts or competing of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"63"}}