{"entities":{"Q790044":{"pageid":791892,"ns":120,"title":"Item:Q790044","lastrevid":48684001,"modified":"2026-01-05T14:47:44Z","type":"item","id":"Q790044","labels":{"en":{"language":"en","value":"Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3847220"}},"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":"Q790044$D65CA816-A178-4FA5-8193-C578FCCC24B5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"44b891b67c32124aca73019aa17543b075a4e7ed","datavalue":{"value":{"text":"Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790044$83275E14-1379-48F0-80D3-2EE0662A4D33","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ff82b75bc8767b9c909007885cf95fd3fcb53812","datavalue":{"value":"0533.90062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790044$881D2D81-C03E-4359-B442-91B690306D96","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"57e18d465ffbee7dc1f886561627c3d7b6c83e04","datavalue":{"value":"10.1016/0166-218X(84)90003-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790044$F4192CB8-A2E2-4F06-9A48-30218CD9CA60","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$FD73936C-6058-4358-8774-D58239F21AB3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q790044$D2468B27-42BA-4FFA-B784-A19A868CA8EE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c0cc714da488b7baa49890e84bbb626a531865e","datavalue":{"value":"A function Z on the power set \\(2^ N\\) of a finite set N is called nondecreasing, if Z(S)\\(\\leq Z(T)\\) for all \\(S\\subset T\\subset N\\), and submodular, if \\(\\rho_ j(S)\\geq \\rho_ j(T)\\) for all \\(j\\in N\\backslash T\\) and \\(S\\subset T\\subset N\\), where \\(\\rho_ j(S)=Z(S\\cup \\{j\\})-Z(S)\\) is the discrete derivative at \\(S\\subset N\\) in direction \\(j\\in N\\). The total curvature of a nondecreasing, submodular set function is the value  \\[  \\alpha =\\max_{j\\in N^*}\\{\\frac{\\rho_ j(\\emptyset)-\\rho_ j(N\\backslash \\{j\\})}{\\rho_ j(\\emptyset)}\\},  \\]  where \\(N^*=\\{j\\in N:\\rho_ j(\\emptyset)>0\\}\\). Now let (N,X) be a matroid and Z a nondecreasing, submodular set function on \\(2^ N\\) satisfying \\(Z(\\emptyset)=0\\). Then for the problem (*) ma\\(x\\{\\) Z(S):\\(S\\in X\\}\\) the greedy algorithm is shown to find a solution with value at least \\(1/(1+\\alpha)\\) times the optimum value, where this bound is best possible. If \\(S^ 0=\\emptyset \\subset S^ 1\\subset...\\subset S^ k\\) (the greedy solution) are the sets which are successively constructed by the greedy algorithm, the greedy curvature of Z is the value  \\[  \\alpha_ G=\\max_{o\\leq i\\leq k-1}\\max_{j\\in N^ i}\\{\\frac{\\rho_ j(\\emptyset)- \\rho_ j(S^ i)}{\\rho_ j(\\emptyset)}\\},  \\]  where \\(N^ i=N^{^*}\\cap \\{j\\in N\\backslash S^ i: S^ i\\cup \\{j\\}\\in X\\}\\). It is shown that under the same assumptions as above the greedy algorithm produces a solution with a value at least \\((1-\\alpha_ G)\\) times the optimum value of (*). Another bound in terms of the rank and the girth of X is given, which generalizes the bounds (e-1)/e for uniform matroids and 1/2 for general matroids. Finally, two tight bounds for the case that (N,X) is a general independence system are given, where the first is \\((1- (1-\\alpha /K)^ k)/\\alpha\\), where K and k are the sizes of a largest resp. smallest maximal indepndent set in X, and the second one is \\(1/(p+\\alpha)\\), p being the minimum number of matroids that must be intersected to obtain X.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790044$E38717EB-0FFC-40B8-B0D9-F1EAAA10F98C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790044$066B16D9-4009-4031-B89F-3CD057DB55B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790044$4B506653-32B8-4BFC-9DF5-3F1CE8A3A654","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"975d774b9fbce220da17e5c1281e7530333ee402","datavalue":{"value":"3847220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790044$BC15AC96-3E40-4490-8445-4A4B60EDB929","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q790044$C6B8454A-F297-4005-8A4E-D4329A804D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3353e7b27f7109a59e8e9274d39fdc011eb0bb0","datavalue":{"value":"submodular set function","type":"string"},"datatype":"string"},"type":"statement","id":"Q790044$6A4D913D-63CF-4242-9E70-EF49A04CDD95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q790044$891A43B2-E2BA-4CBA-A0CB-4AA775D2945A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"741d3a5fca1fb52e392d264e84a73b63feda5c80","datavalue":{"value":"independence system","type":"string"},"datatype":"string"},"type":"statement","id":"Q790044$C9C1C5E6-83A6-4A0A-AD7E-BF0C535D7A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q790044$4FD6FECC-5954-4ABC-A33D-0F2301D56E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"690225eda3faaf5288d73517269d3b5440c7d091","datavalue":{"value":"worst-case bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q790044$A21EAE74-6FE5-464D-94FF-184B7AD565BB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa9a170b566faa650496c61eaa134019d05c6a23","datavalue":{"value":{"entity-type":"item","numeric-id":203960,"id":"Q203960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$5A47B168-F093-4631-9D05-9E8295401AA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"feb07495fa8de76912d587852b3aa20404b344f1","datavalue":{"value":{"entity-type":"item","numeric-id":163019,"id":"Q163019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$5C8183DF-DE57-45CC-948D-866688F1C519","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a45b400d22190ce8d9d8376830240adc5a55cd78","datavalue":{"value":{"entity-type":"item","numeric-id":367043,"id":"Q367043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$1859CA82-4F41-4C3B-83A9-55F473218739","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":"Q790044$B102A6CE-7CE7-4733-AC90-E3BFB5E03F8B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a80eed9f379f185c9ca92aab1fa2ad3cc4463c9","datavalue":{"value":{"entity-type":"item","numeric-id":3887227,"id":"Q3887227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$FFB17A10-79ED-40C5-83B0-67449C6C6437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"671fc2186f91875a44e93a8640df028a0257ad79","datavalue":{"value":{"entity-type":"item","numeric-id":4135210,"id":"Q4135210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$2D6D39AB-82C0-4B22-A6BE-83A318B73443","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":"Q790044$499C14EB-9817-4806-9DDF-7B71389C85F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$CF195445-7854-4F41-A830-7157EA37CD1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca21434ff85b43333fe46c1f5c68b6fca34b2e32","datavalue":{"value":{"entity-type":"item","numeric-id":4196269,"id":"Q4196269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$8E0F2346-A34F-409C-9AE0-0F84BBD7304B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec9478160024c51066b30b445e60340331151e4d","datavalue":{"value":{"entity-type":"item","numeric-id":4119222,"id":"Q4119222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$97101596-3C67-4A6B-811F-833C3D1F6404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2533ca9b57f93e7251fd366784646baeb10e1a3","datavalue":{"value":{"entity-type":"item","numeric-id":4174528,"id":"Q4174528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$76318279-0AE6-45FF-808F-833A944F1C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c35c3c18100f10a76a9ef0d730325b542a65e7","datavalue":{"value":{"entity-type":"item","numeric-id":115238,"id":"Q115238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$0781BAD4-532E-4B8F-BD62-A7CAC89AD035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$AB2D6604-97F1-4C5D-B6D2-C61C276F89FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9524d11e3548fa2018d0863de095cec92224865","datavalue":{"value":{"entity-type":"item","numeric-id":4152030,"id":"Q4152030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$47DD1845-0E8A-4A06-B977-88A9A602FBB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790044$D16B629B-2544-4DC7-B95E-C44BAB08F495","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3bc031882fb983534379be58782ad4d40503989d","datavalue":{"value":"https://doi.org/10.1016/0166-218x(84)90003-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q790044$C143BA16-958A-4FFA-A13B-787A0929C473","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"75cde2712fe75b64e34ccd92c6a21d3f7f4ef833","datavalue":{"value":"W2011193572","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790044$ABE00945-F769-4432-86C0-E315C5296B90","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60b6832ed78db46d90a14ae9614841c7723c73f2","datavalue":{"value":{"entity-type":"item","numeric-id":5963607,"id":"Q5963607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3198cb8d9890b5d1a7919810af9250fc08e4fc1","datavalue":{"value":{"amount":"+0.8733528852462769","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":"Q790044$BAFE2077-FA00-4A3E-A854-FDE3EF53F11B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c26979bf84d93c654e957ab21fff2b59b29480cb","datavalue":{"value":{"entity-type":"item","numeric-id":2999661,"id":"Q2999661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caebe59d83d4d8a0b636ba314f4f73974f4bdf7d","datavalue":{"value":{"amount":"+0.8702424168586731","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":"Q790044$80997662-8DDC-4B4D-9403-A884D5A027A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45e2fdfe4b5cfaada23898f11f6c09c7f8a4b865","datavalue":{"value":{"entity-type":"item","numeric-id":3225171,"id":"Q3225171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6007f8879a61c68a6ced35db422a98266b7669f","datavalue":{"value":{"amount":"+0.852669894695282","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":"Q790044$8F11C791-4E4D-4B46-A5DE-2CC91F8EC4AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb4da91766ff312c51573c625cd4fab25c100410","datavalue":{"value":{"entity-type":"item","numeric-id":5429267,"id":"Q5429267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ed3d7609c1982f5a19fb1fbcae050e2a4afc237","datavalue":{"value":{"amount":"+0.850479245185852","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":"Q790044$22D8187F-97D3-4433-934D-635295A438CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb81d9997991d932a796f17cccb6bfe96a7de408","datavalue":{"value":{"entity-type":"item","numeric-id":5494928,"id":"Q5494928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faa8ac0db5418e9c0c5a5a129749f5c146d16ce1","datavalue":{"value":{"amount":"+0.8375411629676819","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":"Q790044$48CD7FEC-EF29-4A1D-8EFC-A2C9C1EC38C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:790044","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:790044"}}}}}