{"entities":{"Q733910":{"pageid":735759,"ns":120,"title":"Item:Q733910","lastrevid":63966711,"modified":"2026-04-11T16:44:38Z","type":"item","id":"Q733910","labels":{"en":{"language":"en","value":"Greedy algorithms for the minimization knapsack problem: average behavior"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5617854"}},"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":"Q733910$F258841E-9BB3-42F8-AB17-0658BF116F0A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"05543928164cf78be2dff61931b71dd607d3ed52","datavalue":{"value":{"text":"Greedy algorithms for the minimization knapsack problem: average behavior","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q733910$4174FD0D-3E6F-4ABB-BDF2-109D3313474B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1de1015ce7ac20404ef7ce4df83aa5c9ff81a49d","datavalue":{"value":"1192.90166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q733910$C28539EF-8126-453F-BD25-7405AAF59FD9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cf25ce818b85bb8b10c5d233e02ea9e0a830581b","datavalue":{"value":{"entity-type":"item","numeric-id":295575,"id":"Q295575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q733910$54ECF479-F391-4D2A-A98D-88457562D5DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bd476ebbd61c1948a69e599e82439aa1b933a98f","datavalue":{"value":{"time":"+2009-10-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q733910$1564E6E1-F259-4956-BEF6-9602B83594D8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bf91c9e703708dabade8cccb58a264d89930cbb0","datavalue":{"value":"The authors study the average behaviour of primal and dual greedy methods for the solution of the following knapsack problem:  \\[ \\min \\left\\{ \\sum^{n}_{j=1} c_{j}y_{j} \\mid \\sum^{n}_{j=1} a_{j}y_{j} \\geq d, y_{j} \\in \\{0,1\\}, j=1,\\dots,n\\right\\}. \\tag{P} \\]   The coefficients \\(c_{j}, a_{j}\\) are assumed to be independent random variables uniformly distributed over \\([0,1]\\). If \\(\\mathcal{A}_{n}\\) denotes the primal or dual greedy algorithm for the solution of (P), \\(g^{\\mathcal{A}_{n}}\\) the resulting objective function value, and \\(g^{*}\\) the optimal value of (P), \\(\\mathcal{A}_{n}\\) is said \\textit{to have asymptotical tolerance \\(t > 0\\)}, if \\({\\mathbf P}(g^{\\mathcal{A}_{n}}-g^{*} \\leq t) \\rightarrow 1 \\text{ for } n \\rightarrow \\infty\\).   The main result of this paper is the following: If \\(d=\\mu n\\) with \\(\\mu < t/3\\), then the primal and dual greedy methods for (P) have asymptotical tolerance \\(t\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q733910$91A9586C-6DA7-4292-8AB5-DE1BF24AAFBE","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":"Q733910$9C42C4EA-F54C-4CFD-A09E-D7D62C279518","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q733910$3FFCDFEF-D05A-4B8D-885D-EC3B6EB250C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dade3bc82a2f7e555fdd92f6a7aa24c002fcafaf","datavalue":{"value":"90C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q733910$32AB189E-3FC8-4E52-83D4-035FDAAD3080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q733910$5F398055-0AF5-43EA-92A2-381D3938739B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7df48e4dad91ae1981739072dd28df2a6acb4f3f","datavalue":{"value":"5617854","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q733910$199250C1-2A2C-4B09-911D-962EC8AC02F9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"45f9cd1103a38188df6819ffa0de15efc3347b57","datavalue":{"value":{"entity-type":"item","numeric-id":1423698,"id":"Q1423698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q733910$CBC9BAA7-A4DD-4A77-843C-9706B9B45B5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"01073b98f98a4ee44a2f3e494e54631a066d762c","datavalue":{"value":{"entity-type":"item","numeric-id":1423699,"id":"Q1423699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q733910$B5706AD4-5D82-4B72-9604-5562F4490422","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"674cd60828bc007cb59f25ed895882f886c650f9","datavalue":{"value":{"entity-type":"item","numeric-id":17180,"id":"Q17180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q733910$F7A74736-0FCB-428A-97A7-4BA09AACC8D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c999c1a7fc9dbe817177ebd058dccb9f0956e5fe","datavalue":{"value":{"entity-type":"item","numeric-id":16891,"id":"Q16891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q733910$B4B86264-760D-493D-A8F2-14E552C48A0D","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":"Q733910$0CFA9E18-F3BE-4107-ACE4-EB4CBE518BD9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8151ce1172047495584379bdd1905bbd03982248","datavalue":{"value":"https://doi.org/10.1007/s11488-008-1003-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q733910$79425644-9BFD-4A71-BC5F-227F61C248B3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0945c680b92608a2636b3a7062be3cf9e4f59041","datavalue":{"value":"W4229769813","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q733910$3B4E16DD-0CA8-4AB0-BEC2-FDD03C3A3CB9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d673e9ffbb3fb9ddd4a4e184f74fd260b9cbc809","datavalue":{"value":"10.1007/S11488-008-1003-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q733910$8C1592AB-ECFC-4E99-BACC-A5DA8E6410B9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd9bf0d7ec1e2f699eab1d253599252553afd272","datavalue":{"value":{"entity-type":"item","numeric-id":2773680,"id":"Q2773680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea6b9a9768e651ed3a7f527eafc66a6c2141dd9b","datavalue":{"value":{"amount":"+0.9433931","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$12D9EF0B-AFC5-48A0-A5E9-AEBA4433965C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc1e014d443870c2731b6e379d878dfb7e4e056d","datavalue":{"value":{"entity-type":"item","numeric-id":1423700,"id":"Q1423700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64eef918d23373b849ff553ba6fe5f5b14bfd6b6","datavalue":{"value":{"amount":"+0.94337195","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$97A763E7-82E8-4FC6-96BF-14E79A7684DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf3a7414d6195a9da49cfd3049dd39c4c001ce0a","datavalue":{"value":{"entity-type":"item","numeric-id":4233334,"id":"Q4233334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d919f092ed3f05d3d14b5ceb3b5120d960106af1","datavalue":{"value":{"amount":"+0.9333239","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$BEA484CC-7A93-4503-B00E-2FFFEB4BACBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a08963608984e921ddd763da79a6e647f5348b0d","datavalue":{"value":{"entity-type":"item","numeric-id":1811628,"id":"Q1811628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4a4a774a2208065b59629af9468cfc2dea93169","datavalue":{"value":{"amount":"+0.9188528","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$F85E27DF-76F9-4FB1-B15A-8486DFA92B67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d218bc6432c02926489e265919f8251124efe43","datavalue":{"value":{"entity-type":"item","numeric-id":3682239,"id":"Q3682239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"024359a3e10012f48a85631c771a8c59be42a87b","datavalue":{"value":{"amount":"+0.9028556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$AF2F69E4-57C5-4BCB-8418-ED68303F23C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec9ba24c88b79f0b6ff6d01fe8a167a64ab15ad4","datavalue":{"value":{"entity-type":"item","numeric-id":1420409,"id":"Q1420409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96abce08553d22291df5a7ee4c1dc4b9dac3fe9a","datavalue":{"value":{"amount":"+0.9005862","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$9DE4411D-FF30-472D-AC3C-FCBD8C1CBED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"907bf0dcbfb5f0599bb0b7673de6fd00863afcfa","datavalue":{"value":{"entity-type":"item","numeric-id":4327882,"id":"Q4327882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05b33cda7eb5f1f8770305a0e30ebc55914251a2","datavalue":{"value":{"amount":"+0.8842728","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$BA5FCCED-B0BE-4893-B677-929D2730E07A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a586699bb6290cc9e8d38f158ed952da3a0303f6","datavalue":{"value":{"entity-type":"item","numeric-id":3330975,"id":"Q3330975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af7cf037e9fd4b74deda55a198ed0d524b1bd9e4","datavalue":{"value":{"amount":"+0.882329","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$852B4F0E-9552-4606-9993-4E903E80780E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b121f953fa9ec9b4319ba62301934b670a2fcc11","datavalue":{"value":{"entity-type":"item","numeric-id":1761999,"id":"Q1761999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"888b272b2888b422d4f3a7b0c38d231ed76ca6e2","datavalue":{"value":{"amount":"+0.87957025","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$FCBE6588-8F2D-407B-9101-57F2538041DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01fbe8ed7e496642f43de3e4c8f4298dbc18dddf","datavalue":{"value":{"entity-type":"item","numeric-id":5753744,"id":"Q5753744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c41a9afa98a4e53cdf771819cb91cae00780c0e","datavalue":{"value":{"amount":"+0.8762883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q733910$4A811902-E41F-4E64-8A8D-547591C6BE52","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Greedy algorithms for the minimization knapsack problem: average behavior","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Greedy_algorithms_for_the_minimization_knapsack_problem:_average_behavior"}}}}}