{"entities":{"Q2220660":{"pageid":2231403,"ns":120,"title":"Item:Q2220660","lastrevid":82664093,"modified":"2026-05-06T21:26:52Z","type":"item","id":"Q2220660","labels":{"en":{"language":"en","value":"New polyhedral and algorithmic results on greedoids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7300740"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$59EBEE58-A093-4E5C-B08C-5CA356F2DA62","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"903370e62114c997ab0aa5ca69bb8f865fbfd3a6","datavalue":{"value":{"text":"New polyhedral and algorithmic results on greedoids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2220660$0903CA0A-E92E-45DB-B533-F592833000FE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"69afb9e958fbdfe6013111d1d6350fa53969df5d","datavalue":{"value":"1462.90113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2220660$6828645E-9898-49F8-B802-B991E865FCBC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83fde8e460521ab354601f45df45e430d78f270f","datavalue":{"value":{"entity-type":"item","numeric-id":507325,"id":"Q507325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$6920AF66-50D5-4C91-9E53-F41C67203178","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$28385417-7538-4662-83F2-F925CEE3F7A6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c0827198be489c99d5ba6559ec16692e838cc43b","datavalue":{"value":{"time":"+2021-01-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2220660$543B3FFA-8DD8-4377-BEA1-7F914B83A719","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"02accd92e39d8f52e9718aeed590cdb02da4bee3","datavalue":{"value":"https://arxiv.org/abs/1811.04690","type":"string"},"datatype":"url"},"type":"statement","id":"Q2220660$3E118083-E896-44BF-AB23-BF527122124E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dbd625c054504cd5ef05da09125ac9a103ab2db8","datavalue":{"value":"The paper defines a new class of greedoids named \\textit{local forest greedoids}, that includes both matroids and branching greedoids. The first result of the paper is a generalization of a fundamental Edmonds' classic theorem on the polytope spanned by incidence vectors of independent sets of a matroid. A generalization of an eqivalent formulation of this theorem to local forest greedoids is proved.  The next part of the paper deals with the attacker-defender game named the Matroid Base Game. It is a two-player, zero sum game in which the Attacker chooses an element of the ground set of a given matroid and the Defender chooses a base of the same matroid. The payoff depends on both of their choices in such a way that it is favorable for the Attacker if his chosen element belongs to the base chosen by the Defender. In this paper, the authors further generalize the definition of the Matroid Base Game by replacing matroids with local forest greedoids and prove that some of the results of \\textit{D. Szeszl\u00e9r} [Math. Program. 161, No. 1--2 (A), 347--364 (2017; Zbl 1366.91006)] generalize to this case too. They also show that this more general framework is capable of handling and generalizing some further graph reliability metrics known from the literature beyond the ones already contained in the framework provided by the matroid base game.  Finally, the paper analyses known results about the conditions under which the greedy algorithm is optimal on greedoids. The authors analyse in particular results of [\\textit{B. Korte} et al., Greedoids. Berlin: Springer (1991; Zbl 0733.05023)] and identify some false claims there. These mistakes are pointed out and corrections are proposed and proved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2220660$B1294516-95BD-462D-BEAB-D1911CDB152E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$EF1899C3-EF0F-4A98-8E09-9E4B4020428C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2220660$BEAD0339-9E68-4AEB-9218-13BD1DABDD91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5c83f057600e5614b7fec59c8e4ac61cb41ba8d","datavalue":{"value":"91A80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2220660$F90C683D-AE7E-42C7-86F5-0BE5BD6C185F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d60eacb48acb8f5b0960303eda6f819d3d2acec1","datavalue":{"value":"7300740","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2220660$03E9B0F7-F1B6-4A20-BD41-3164283DA6CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"050ba1bd2fa71542fb51d02ae13a113a80aa0411","datavalue":{"value":"greedoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q2220660$6B8F0D6C-4882-43AB-960D-50993EC9CF7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53dde8b387b5cd23f4abb2e117e873f60004406d","datavalue":{"value":"Nash equilibrium","type":"string"},"datatype":"string"},"type":"statement","id":"Q2220660$C351928E-56A2-49FE-AE7C-D7F200D7DA65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q2220660$978AD334-16BE-4AF8-AADD-D3423BDA5326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84c612e97d0bbc5f0fc0c1fc6c648d85c6d9bbe2","datavalue":{"value":"security","type":"string"},"datatype":"string"},"type":"statement","id":"Q2220660$F473FCCF-2999-42DF-B4DD-EDE39A551C61","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$66091E96-329D-4183-AD82-F6734EA90AD1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e4d50c24a6e88e65ff0a7426093d4a37bc58e715","datavalue":{"value":"W3101203563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2220660$427D2560-3C3B-4CD9-AD42-57064A4D55B7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7453f5f4af7e74c9de4a1dd6e3c5170033d8a71","datavalue":{"value":{"entity-type":"item","numeric-id":666676,"id":"Q666676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$C473C089-4CEE-48C3-A102-710178623398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a61c7e6a4eca4c8326f209648cf678600672b938","datavalue":{"value":{"entity-type":"item","numeric-id":3767103,"id":"Q3767103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$61E9C0EF-C26C-4335-A648-F4BBA8A04868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4042a6a8925d33e7ac25ffe3a11c3e8654542cc4","datavalue":{"value":{"entity-type":"item","numeric-id":5668601,"id":"Q5668601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$AAA6AF02-2920-4D48-A5B9-F9CF505EDCF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4e7fefb3e484dfdc7c368bbe54543169fcb1dee","datavalue":{"value":{"entity-type":"item","numeric-id":4695388,"id":"Q4695388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$3FFDED73-7E7D-4CB4-AA10-E94E35EBBEE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb4372858ea2a827f2ef19aa737d76f082fef214","datavalue":{"value":{"entity-type":"item","numeric-id":3338268,"id":"Q3338268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$9E39B2C8-F22C-48FF-8D6A-6601ADAB5CA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9321fa0d3d838ff71f827d3db6dc7538a7f5e718","datavalue":{"value":{"entity-type":"item","numeric-id":3323971,"id":"Q3323971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$33798385-FE42-4B26-9CC8-896453917DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd8097640b1f4ba9eec43837bd81d298e8358613","datavalue":{"value":{"entity-type":"item","numeric-id":810029,"id":"Q810029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$3A54BA68-392F-4EA4-A7C2-A602CAB2A928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d00ed1a006b784e393a87f7c34e24d4c6908fc3","datavalue":{"value":{"entity-type":"item","numeric-id":2840919,"id":"Q2840919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$DC436307-5B1A-420D-866A-141A78A615FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69c713a6155f14f1fc02b289cf4fd38a5c0d915f","datavalue":{"value":{"entity-type":"item","numeric-id":1644861,"id":"Q1644861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$BE8B4DBD-F7A1-4313-901F-730062D64CF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62bd4d3065b72755d22cf1915f9523124f5efe9f","datavalue":{"value":{"entity-type":"item","numeric-id":1103626,"id":"Q1103626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$CFE17DA1-DDDF-4B11-926A-0B737857A085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c01149a6900c0f611a509645affd60c9a396109","datavalue":{"value":{"entity-type":"item","numeric-id":1854113,"id":"Q1854113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$7848D0E2-DAF2-4F77-8D19-B026B6777767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f287870eccf7faeb8d02d9b056f934e0b6d8cf02","datavalue":{"value":{"entity-type":"item","numeric-id":507326,"id":"Q507326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$5A2D0002-69FE-4924-88C6-D33F2F1D6B12","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"869caec00a70fc92080e9ce37607a4f5465aabf9","datavalue":{"value":"Q127331467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2220660$BEFBAD21-92B2-4054-B14C-2DB3E118384B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"50729979cddfd623de47901fb5480c68c643b9cb","datavalue":{"value":"10.1007/S10107-019-01427-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2220660$B14D12E5-239A-4264-9C3A-3CF170503984","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b30ba4d0f3f808162f1547674c491bc9a0957ed","datavalue":{"value":{"entity-type":"item","numeric-id":3323971,"id":"Q3323971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f095f6a0c13a41493f067bae28b2474260b5906","datavalue":{"value":{"amount":"+0.7872836","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$C95E2BCE-7AC4-4F07-A455-EA0FB91EFF57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48bd95112105fba6180b871a90d314d1ae2a45c1","datavalue":{"value":{"entity-type":"item","numeric-id":507326,"id":"Q507326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5ab783cd4390bcc3b86662896bc850fe64a45c1","datavalue":{"value":{"amount":"+0.76770556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$DF29CFCC-8D35-4DE1-B98B-47EA89925212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbfe5a3977d3679c5b6a05320c3c14081e6e5aa2","datavalue":{"value":{"entity-type":"item","numeric-id":666676,"id":"Q666676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35f1d73b8e45b1f3b9b5694343d99ab573af4035","datavalue":{"value":{"amount":"+0.7450509","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$DBD23856-52E4-4DA6-954C-A7AF2F78A0D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7ea4008dd9db4aa2d2515500768f770703b3183","datavalue":{"value":{"entity-type":"item","numeric-id":2168727,"id":"Q2168727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af35bc18288439a8ec84e69ae0045b2d6470ff55","datavalue":{"value":{"amount":"+0.73520124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$C559ACE4-9EFE-4612-B8F6-40356BC23491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f75d805aa0b829739b7e2fde8ed84902fd00dfae","datavalue":{"value":{"entity-type":"item","numeric-id":1575071,"id":"Q1575071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e52263ff59ed39b52a368dfc4ccc9cfe2d2e2d4","datavalue":{"value":{"amount":"+0.7322165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$F25D4D8D-BD58-413F-B01E-4C5D7DCAF53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"904be3d183b51ca72c3d417e345424331523b0c2","datavalue":{"value":{"entity-type":"item","numeric-id":4012035,"id":"Q4012035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25fcc761a64300cc92ade8453b517c3dedb8b519","datavalue":{"value":{"amount":"+0.723799","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$71E34324-E0C5-44D6-A8BD-484B45BF3899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227a37da133c3768aa73f374a7161ceac3baed38","datavalue":{"value":{"entity-type":"item","numeric-id":1864590,"id":"Q1864590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b65eb42daf4f74d74659990c7bb2b1570b3c7294","datavalue":{"value":{"amount":"+0.722398","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$B545160A-A240-4BDD-8D1C-79CC41D93552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f2e7e3b98185b7e43d8982a2a997962acaccd22","datavalue":{"value":{"entity-type":"item","numeric-id":2773612,"id":"Q2773612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de5c9e3d189faa1e5a769acca86ed77467fbe799","datavalue":{"value":{"amount":"+0.7212534","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$B670A7E4-32B5-4A85-986A-B699EB217258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20c85c9ee115e258304c3d5ae22482ec55b05fa9","datavalue":{"value":{"entity-type":"item","numeric-id":3470255,"id":"Q3470255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"642481af38e24c855b8af1484a88246235331960","datavalue":{"value":{"amount":"+0.7208555","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2220660$86D2A17F-F17A-40A4-A33E-C5C46BABB4A3","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2220660$91A84251-D1E9-46FC-A4DB-2662A335A16E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New polyhedral and algorithmic results on greedoids","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/New_polyhedral_and_algorithmic_results_on_greedoids"}}}}}