{"entities":{"Q1193543":{"pageid":1204292,"ns":120,"title":"Item:Q1193543","lastrevid":66823278,"modified":"2026-04-12T13:06:15Z","type":"item","id":"Q1193543","labels":{"en":{"language":"en","value":"Greedy algorithm compatibility and heavy-set structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 64834"}},"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":"Q1193543$A131C9C9-2299-44D1-B755-4E4F0B2F68B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4e8350c22e1eca124bd6bf935070b4575911c72a","datavalue":{"value":{"text":"Greedy algorithm compatibility and heavy-set structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1193543$A431D2BE-BDCD-49E6-8638-7F0A6FE75E2E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"373ad2a7defcd9c8bc30103b54d22fdb7685c3d0","datavalue":{"value":"0768.05021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193543$43C3F592-B186-4A3D-9CFF-60482050A1EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3e721611c6ec5fa01ba0804d14365705262e43e","datavalue":{"value":"10.1016/0195-6698(92)90039-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193543$6E3BEBC1-08DE-46F7-8978-159B42A1A348","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"39319ff5a541effd2561c7a324e2091a1d5eb307","datavalue":{"value":{"entity-type":"item","numeric-id":1193541,"id":"Q1193541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193543$E6C96F85-1023-4E11-8475-FC37500039E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fce259a87d28548ca5ac5f4cee31baa7f55a3205","datavalue":{"value":{"entity-type":"item","numeric-id":392432,"id":"Q392432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193543$29E840BF-85F6-44CF-AA9E-6712988F5FF8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193543$78B78648-694F-4843-A155-25AC51D5D1C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1193543$38F6B77C-629B-4FE4-A576-CAF7B352ED7D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a85c8ca6a8454ed8019d6df8c64626a2bbced0d5","datavalue":{"value":"The paper considers a relation between the set structure called strong greedoid and the possibility of using the greedy algorithm for finding an optimal solution. A strong greedoid is defined as a set system \\((E,{\\mathcal E})\\) with the following properties:   (1) \\(\\varnothing\\in{\\mathcal E}\\);   (2) if \\(A\\in{\\mathcal E}\\) and \\(A\\neq\\varnothing\\) then there exists \\(a\\in A\\) with \\(A-\\{a\\}\\in{\\mathcal E}\\);   (3) if \\(X,Y\\in{\\mathcal E}\\) and \\(X=Y+1\\) then there exists \\(x\\in X-Y\\) with \\(Y\\cup\\{x\\}\\in{\\mathcal E}\\).   It is shown that every strong greedoid is greedy algorithm compatible, that means a greedy algorithm chooses a sequence of sets \\(\\varnothing\\subset A_ 1\\subset\\cdots\\subset A_ n\\) where \\(A_ r\\) is a heaviest independent set of cardinality \\(r\\) with respect to a given weight function. Moreover, any sequence of heaviest sets of a given strong greedoid can be obtained by the greedy algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193543$90EC3A42-12F8-493A-A03F-1A4CF98FF969","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193543$EB52B15C-A42A-44DB-B75C-58EC70A1F5BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193543$236C7650-F0CB-4840-B19A-CAD7C7AC6B82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193543$93236A01-71BB-4390-B5B2-B3BDB1D63208","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eca710b2803b8ce8488d9a8a861bbae18d1d1c59","datavalue":{"value":"64834","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193543$7CEB3207-77A8-4E0F-8987-EB1714BADAE7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193543$74B97B26-BC77-413C-BCCC-3D01293DFB71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3a9d8e2f8bae9d410a27fd14d8dca43a2d8be4a","datavalue":{"value":"strong greedoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193543$2BBA96B5-9F05-4E97-A59E-4059233B720D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193543$A1E17AD6-6166-4FB1-A861-0DA2AC0277AD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"15fb7789dd0d1691819f44cebdb975938d5b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":967347,"id":"Q967347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193543$300118E5-FBC0-4D9A-833D-CBB1E12C0A74","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":"Q1193543$2F341F38-1908-45BB-A0D4-CFC9508E3684","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b7302ff69b2dbfaa8c903aa9bdb64d3730736332","datavalue":{"value":"https://doi.org/10.1016/0195-6698(92)90039-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1193543$5717F01B-86F1-4510-87AB-9DC6B7E3B288","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9888d68443a25f3c5dd1b812e0e941b66f84bfa1","datavalue":{"value":"W2061515687","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193543$5112EE33-4A23-482B-9C21-2E5B6FE138C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b823415af95e85e7aa983ef0ddfc870086e66349","datavalue":{"value":{"entity-type":"item","numeric-id":3874222,"id":"Q3874222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193543$0D7514DE-3D57-4741-B479-5B768AFF6A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d794f9ab4e0538d34f55f04cca4cd0f1781a4993","datavalue":{"value":{"entity-type":"item","numeric-id":1082346,"id":"Q1082346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193543$DB452C3B-D904-4C3B-A966-63E3A544D0FE","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":"Q1193543$1048CD43-F18D-467A-94C3-B94DEE5CAC97","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb4b135992bfc28331ecb94ddaf0713b26e82c81","datavalue":{"value":{"entity-type":"item","numeric-id":4038320,"id":"Q4038320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f8c4bc6a85e4d428b48e7a608f8710579503dfe","datavalue":{"value":{"amount":"+0.8107880353927612","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193543$BF069CCE-2851-48EE-B1CF-C9B583E4CB74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bd59fc2573aa579419288144033e9098fcb26de","datavalue":{"value":{"entity-type":"item","numeric-id":3970969,"id":"Q3970969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36d260360726273325aae1fe36206393db21f669","datavalue":{"value":{"amount":"+0.8086658716201782","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193543$4633ECB3-BFE2-468A-AAD5-F2B278F391DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0a3921d95f435d1726e79ffa14fe272b930f699","datavalue":{"value":{"entity-type":"item","numeric-id":1102299,"id":"Q1102299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fa379c822cbec2406a8012096f229fa2ca1b53d","datavalue":{"value":{"amount":"+0.8030964732170105","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193543$C7F43359-0DB1-450F-9C98-D97D29FFCA65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15fc2a0c3e513865e7e735e3fe75f909cd0ac8af","datavalue":{"value":{"entity-type":"item","numeric-id":810029,"id":"Q810029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"799d6ae3bf33ef90a861c5b0e496c2709f217839","datavalue":{"value":{"amount":"+0.8024904131889343","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193543$BD53DB8F-9F69-4ECA-926A-16FDB1E3D85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f28a8b868f6429aef7825e641003a7529b5661d","datavalue":{"value":{"entity-type":"item","numeric-id":1613405,"id":"Q1613405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"befc25df89312ac417a46c1d28b49dea07af66b0","datavalue":{"value":{"amount":"+0.7970420122146606","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193543$3D5BE7A2-9F99-4E89-A2E0-A6F4016AB469","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Greedy algorithm compatibility and heavy-set structures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Greedy_algorithm_compatibility_and_heavy-set_structures"}}}}}