{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T22:05:01Z","timestamp":1768082701105,"version":"3.49.0"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005881","name":"Emberi Eroforr\u00e1sok Miniszt\u00e9riuma","doi-asserted-by":"publisher","award":["BME FIKP-MI\/SC"],"award-info":[{"award-number":["BME FIKP-MI\/SC"]}],"id":[{"id":"10.13039\/501100005881","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["OTKA 124171"],"award-info":[{"award-number":["OTKA 124171"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Greedy algorithms are among the most elementary ones in theoretical computer science and understanding the conditions under which they yield an optimum solution is a widely studied problem. Greedoids were introduced by Korte and Lov\u00e1sz at the beginning of the 1980s as a generalization of matroids. One of the basic motivations of the notion was to extend the theoretical background behind greedy algorithms beyond the well-known results on matroids. Indeed, many well-known algorithms of a greedy nature that cannot be interpreted in a matroid-theoretical context are special cases of the greedy algorithm on greedoids. Although this algorithm turns out to be optimal in surprisingly many cases, no general theorem is known that explains this phenomenon in all these cases. Furthermore, certain claims regarding this question that were made in the original works of Korte and Lov\u00e1sz turned out to be false only most recently. The aim of this paper is to revisit and straighten out this question: we summarize recent progress and we also prove new results in this field. In particular, we generalize a result of Korte and Lov\u00e1sz and thus we obtain a sufficient condition for the optimality of the greedy algorithm that covers a much wider range of known applications than the original one.<\/jats:p>","DOI":"10.1007\/s10878-021-00833-y","type":"journal-article","created":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T03:02:40Z","timestamp":1638154960000},"page":"287-302","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Sufficient conditions for the optimality of the greedy algorithm in greedoids"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8159-0839","authenticated-orcid":false,"given":"D\u00e1vid","family":"Szeszl\u00e9r","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,29]]},"reference":[{"key":"833_CR1","unstructured":"Boyd EA (1988) A combinatorial abstraction of the Shortest Path Problem and Its Relationship to Greedoids, CAAM Technical Report, 30 pages"},{"issue":"1","key":"833_CR2","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J Edmonds","year":"1971","unstructured":"Edmonds J (1971) Matroids and the greedy algorithm. Math Program 1(1):127\u2013136","journal-title":"Math Program"},{"key":"833_CR3","doi-asserted-by":"crossref","unstructured":"Korte B, Lov\u00e1sz L (1981) Mathematical Structures Underlying Greedy Algorithms. In: G\u00e9cseg F (ed) Fundamentals of Computation Theory, , FCT81. Lecture Notes in Computer Science (117), Springer, Berlin, Heidelberg, pp 205\u2013209","DOI":"10.1007\/3-540-10854-8_22"},{"key":"833_CR4","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/B978-0-12-566780-7.50019-2","volume-title":"Progress in combinatorial optimization","author":"B Korte","year":"1984","unstructured":"Korte B, Lov\u00e1sz L (1984) Greedoids - a structural framework for the greedy algorithm. In: Pulleyblank W (ed) Progress in combinatorial optimization. Academic Press, London, pp 221\u2013243"},{"issue":"2","key":"833_CR5","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/0605024","volume":"5","author":"B Korte","year":"1984","unstructured":"Korte B, Lov\u00e1sz L (1984) Greedoids and linear objective functions. SIAM J Algebraic Dis Methods 5(2):229\u2013238","journal-title":"SIAM J Algebraic Dis Methods"},{"key":"833_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58191-5","volume-title":"Greedoids","author":"B Korte","year":"1991","unstructured":"Korte B, Lov\u00e1sz L, Schrader R (1991) Greedoids. Springer-Verlag, Berlin"},{"issue":"5","key":"833_CR7","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1287\/mnsc.19.5.544","volume":"19","author":"EL Lawler","year":"1973","unstructured":"Lawler EL (1973) Optimal sequencing of a single machine subject to precedence constraints. Manag Sci 19(5):544\u2013546","journal-title":"Manag Sci"},{"issue":"1","key":"833_CR8","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10107-019-01427-7","volume":"185","author":"D Szeszl\u00e9r","year":"2021","unstructured":"Szeszl\u00e9r D (2021) New polyhedral and algorithmic results on greedoids. Math Program 185(1):275\u2013296","journal-title":"Math Program"},{"key":"833_CR9","unstructured":"Szeszl\u00e9r D (2019) Optimality of the Greedy Algorithm in Greedoids, Proc. 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, 438-445"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00833-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00833-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00833-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T07:28:15Z","timestamp":1659079695000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00833-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,29]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["833"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00833-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,29]]},"assertion":[{"value":"5 November 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Data sharing not applicable to this article as no datasets were generated or analysed during the current study.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability of data and material"}}]}}