{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T09:13:02Z","timestamp":1760346782411,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T00:00:00Z","timestamp":1566777600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T00:00:00Z","timestamp":1566777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["185101"],"award-info":[{"award-number":["185101"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"name":"New Hungary Development Plan","award":["T\u00c1MOP-4.2.1\/B-09\/1\/KMR-2010-0002"],"award-info":[{"award-number":["T\u00c1MOP-4.2.1\/B-09\/1\/KMR-2010-0002"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present various new results on greedoids. We prove a theorem that generalizes an equivalent formulation of Edmonds\u2019 classic matroid polytope theorem to local forest greedoids\u2014a class of greedoids that contains matroids as well as branching greedoids. We also describe an application of this theorem in the field of measuring the reliability of networks by game-theoretical tools. Finally, we prove new results on the optimality of the greedy algorithm on greedoids and correct some mistakes that have been present in the literature for almost 3 decades.<\/jats:p>","DOI":"10.1007\/s10107-019-01427-7","type":"journal-article","created":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T07:02:42Z","timestamp":1566802962000},"page":"275-296","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["New polyhedral and algorithmic results on greedoids"],"prefix":"10.1007","volume":"185","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":[[2019,8,26]]},"reference":[{"issue":"3","key":"1427_CR1","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1007\/s00453-018-0466-x","volume":"81","author":"M Ba\u00efou","year":"2019","unstructured":"Ba\u00efou, M., Barahona, F.: Faster algorithms for security games on matroids. Algorithmica 81(3), 1232\u20131246 (2019)","journal-title":"Algorithmica"},{"key":"1427_CR2","unstructured":"Boyd, E.A.: A Combinatorial Abstraction of the Shortest Path Problem and Its Relationship to Greedoids, CAAM Technical Report, 30 pages (1988)"},{"issue":"3","key":"1427_CR3","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/3828.3829","volume":"32","author":"WH Cunningham","year":"1985","unstructured":"Cunningham, W.H.: Optimal attack and reinforcement of a network. J. ACM (JACM) 32(3), 549\u2013561 (1985)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"1427_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1(1), 127\u2013136 (1971)","journal-title":"Math. Program."},{"key":"1427_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/0406021","volume":"6","author":"P Helman","year":"1993","unstructured":"Helman, P., Moret, B.M.E., Shapiro, H.D.: An exact characterization of greedy structures. SIAM J. Discrete Math. 6, 274\u2013283 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"1427_CR6","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.: Greedoids\u2014a structural framework for the greedy algorithm. In: Pulleyblank, W. (ed.) Progress in Combinatorial Optimization, pp. 221\u2013243. Academic Press, London (1984)"},{"issue":"2","key":"1427_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/0605024","volume":"5","author":"B Korte","year":"1984","unstructured":"Korte, B., Lov\u00e1sz, L.: Greedoids and linear objective functions. SIAM J. Algebr. Discrete Methods 5(2), 229\u2013238 (1984)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"1427_CR8","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.: Greedoids. Springer, Berlin (1991)"},{"key":"1427_CR9","doi-asserted-by":"crossref","unstructured":"Laszka, A., Szeszl\u00e9r, D., Butty\u00e1n, L.: Game-theoretic Robustness of Many-to-one Networks. In: Proceedings of Game Theory for Networks: Third International ICST Conference, GameNets 2012, Vancouver, Canada, pp. 88\u201398. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-35582-0_7"},{"key":"1427_CR10","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1515\/math-2018-0026","volume":"16","author":"H Mao","year":"2018","unstructured":"Mao, H.: A greedy algorithm for interval greedoids. Open Math. 16, 260\u2013267 (2018)","journal-title":"Open Math."},{"key":"1427_CR11","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0095-8956(88)90067-6","volume":"45","author":"W Schmidt","year":"1988","unstructured":"Schmidt, W.: A characterization of undirected branching greedoids. J. Comb. Theory Ser. B 45, 160\u2013184 (1988)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1427_CR12","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"issue":"1","key":"1427_CR13","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10107-016-1011-9","volume":"161","author":"D Szeszl\u00e9r","year":"2017","unstructured":"Szeszl\u00e9r, D.: Security games on matroids. Math. Program. 161(1), 347\u2013364 (2017)","journal-title":"Math. Program."},{"key":"1427_CR14","unstructured":"Szeszl\u00e9r, D.: Measuring graph robustness via game theory. In: Proceedings of 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, pp. 473\u2013482 (2017)"},{"key":"1427_CR15","unstructured":"Szeszl\u00e9r, D.: Optimality of the greedy algorithm in greedoids. In: Proceedings of 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, pp. 438\u2013445 (2019)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01427-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01427-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01427-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T15:53:35Z","timestamp":1610985215000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01427-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,26]]},"references-count":15,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["1427"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01427-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2019,8,26]]},"assertion":[{"value":"9 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}