{"entities":{"Q1803680":{"pageid":1814422,"ns":120,"title":"Item:Q1803680","lastrevid":72700017,"modified":"2026-04-14T06:37:15Z","type":"item","id":"Q1803680","labels":{"en":{"language":"en","value":"A class of generalized greedy algorithms for the multi-knapsack problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 221658"}},"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":"Q1803680$80D530AE-CD00-464F-AF6A-62BC3FEA2305","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0c7d17c3203c820cea006c7f1a0a50142eb93136","datavalue":{"value":{"text":"A class of generalized greedy algorithms for the multi-knapsack problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1803680$B0157CE1-2057-4649-9D0A-40E9E2C62623","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"59d96b53cd34e6ef6b8751494bd7d263db929e6e","datavalue":{"value":"0785.90072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803680$673A117A-5CE7-4792-913C-A78BB4E3E937","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b05c3bab6bd031be3b957f3e2d9e968203a452ae","datavalue":{"value":"10.1016/0166-218X(93)90051-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803680$9B0510E3-08EE-405B-9862-357785DEABF0","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":"Q1803680$F6602F8F-CFC8-4F2B-9FCC-C917116EF3DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1803680$5E22CCB5-A52F-4536-8BC1-8710D47EC6CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"88affd86f3f8f502294407aedb049c892da452f0","datavalue":{"value":"A class of algorithms is proposed for determining approximate solutions of the following problem: given nonnegative reals \\(c_ j\\), \\(a_{ij}\\), \\(b_ i\\), find \\(\\max \\sum^ n_{j=1} c_ j x_ j\\), s.t. \\(\\sum^ n_{j=1} a_{ij} x_ j\\leq b_ i\\) for \\(i=1,2,\\dots,m\\), \\(x_ j\\in\\{0,1\\}\\) for \\(j=1,2,\\dots,n\\). The algorithms choose weights \\(w_ 1,w_ 2,\\dots,w_ m\\) and determine nonzero values of \\(x_ j\\) in the order defined by the decreasing ratios \\(c_ j/\\sum^ m_{i=1} w_ i a_{ij}\\).   The authors investigate the complexity of computing a set of weights which gives the maximum greedy solution value. The heuristics are subjected to both a worst case and a probabilistic performance analysis. It is shown that an upper bound on the worst-case absolute difference between the optimal solution value and maximum greedy solution value is less than \\(m\\) \\(c_{\\max}\\). Finally, it is proved that the sequence \\(\\{z^ H_ n(\\lambda^*)/z^ I_ n\\}\\) converges to 1 with probability one, where \\(z^ H_ n(\\lambda^*)\\) is the random variable denoting the solution value determined by the algorithm and \\(z^ I_ n\\) is the random variable denoting the optimal solution of the problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803680$0386FF4B-CEF3-43DD-9177-F87D0C27A04A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803680$EA575603-D6CC-4A2D-A14B-63D6C743C9CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803680$58056E12-D9F8-4FFB-9174-F1FDB03B7895","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b7299a2aea235dbdc9ae3b247bcc7666b5b9fbd9","datavalue":{"value":"221658","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803680$D20C5AEE-3B43-473C-B4B2-8B2977C28063","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d9244f232859d66b963ffa647d807b81fb32b58","datavalue":{"value":"generalized greedy algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803680$2AB2F182-5CCF-4EF0-93F2-52EC31435CEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afdd31348bbb6fcf9e4bf53cf8b02b267a0031da","datavalue":{"value":"multi-knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803680$36DC626F-2D6B-4CAC-8BF4-CAF6B0B6C4CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8205005c0975ece57da73400ce9be01687bc47fd","datavalue":{"value":"approximate solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803680$8682C89A-1307-4578-8436-FBC258ED9BAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803680$82633256-F1DF-42C1-8C68-21535AF70E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba48612399fee59631e9cb955dde3f5bafbd6068","datavalue":{"value":"worst case","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803680$E932B30E-ED43-4E81-8FB1-9AA7A36B56A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37e71542a13753b569182c0141d77234a3562efb","datavalue":{"value":"probabilistic performance analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803680$EC38906B-47A2-4216-8A3D-A166DB464D96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1803680$0BDB5F6A-7942-4416-9A85-F366A9072D6B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"15553ac1624d90cf309324297b60650885a8479b","datavalue":{"value":{"entity-type":"item","numeric-id":689139,"id":"Q689139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$573390E3-5FBD-43C1-A6D8-7C8D1926A9BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"35d6c381bbdf214787241481b862171fcb337669","datavalue":{"value":{"entity-type":"item","numeric-id":627159,"id":"Q627159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$2EE957E4-5E80-47BE-8E23-F15D89CC978D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bd39037057f92722ad655aadbeb0b016d9c1d59","datavalue":{"value":{"entity-type":"item","numeric-id":797496,"id":"Q797496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$854F9CDD-9B3E-42F8-8053-79B3E1AF143E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2b972ef175b4299fdbfc53bb71881ff0c6d5f85c","datavalue":{"value":{"entity-type":"item","numeric-id":587047,"id":"Q587047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$A898BDB0-C4A8-41C2-8C25-6112F5489F05","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":"Q1803680$CF407816-8275-4AF0-B35D-21A44FB39515","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1e3627f13890a3338bad7f8ce5235036336ff8","datavalue":{"value":{"entity-type":"item","numeric-id":3964325,"id":"Q3964325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$E1785B95-2718-4C15-A51D-7E7E282E18E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d873eb220f9c7b9bab911767ca34bf21b911b7c8","datavalue":{"value":{"entity-type":"item","numeric-id":789319,"id":"Q789319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$FDD97C88-25B8-4A56-A23D-EEC470C2248E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$33FC7904-32F0-49C3-AD1B-CA7557F19398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$6EC860DA-916A-4508-A271-59A1C047897E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"480228c429fee5c5e4e1680a67cb389261d7e086","datavalue":{"value":{"entity-type":"item","numeric-id":3912008,"id":"Q3912008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$782B662C-8734-44BB-BF5B-16488EE37F3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb82af502076a1eecf0c35b635418bce63d53e69","datavalue":{"value":{"entity-type":"item","numeric-id":3959309,"id":"Q3959309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$AE72002C-BBD1-4BDC-8078-90A41225D228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b02c1289549043a853312447abaadb43d0addd9","datavalue":{"value":{"entity-type":"item","numeric-id":3792481,"id":"Q3792481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$4DD2DBAA-BAEC-428D-A5A2-D23E1DFB94CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90ceda43b41979357cbe3a55aa9ca127d1624a80","datavalue":{"value":{"entity-type":"item","numeric-id":1804369,"id":"Q1804369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$252B08D6-8B0A-4484-823B-A724CCCF3DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f97331dd7959428ac2deb95fa0862be02620f47","datavalue":{"value":{"entity-type":"item","numeric-id":909581,"id":"Q909581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1803680$692F116F-4E46-40A0-9D83-DABD825B2E71","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f72124d523d2b9f0ed38979299b6daf81648005","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90051-o","type":"string"},"datatype":"url"},"type":"statement","id":"Q1803680$6E69FC3E-1CFF-4890-B375-7CA240D9C80B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9269acb7b12999ed3ad4b79a744bc2d518c3b03d","datavalue":{"value":"W2077554072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1803680$ADB2EE22-659C-45E8-A7D7-DD33069819AA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03cdc440c1cfbfbe19e4941f22902f3376631e23","datavalue":{"value":{"entity-type":"item","numeric-id":3471851,"id":"Q3471851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce027901035a4f03650a0f22a60c0f9f5c5d5c6b","datavalue":{"value":{"amount":"+0.8495185375213623","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":"Q1803680$6EA147F2-8F5A-4B8F-A7E8-C5E1CDE37819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e02f5034aeafcf2dbdb066c621e188e19a2aedf9","datavalue":{"value":{"entity-type":"item","numeric-id":789319,"id":"Q789319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15458ea4f1e8776268682fb7d83789b71c52eac7","datavalue":{"value":{"amount":"+0.8355605006217957","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":"Q1803680$9A614452-19CD-40C1-94BC-D5F917EED8E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"746a2c12ebd7f1b38639c0544503ae01b41a1a02","datavalue":{"value":{"entity-type":"item","numeric-id":3792480,"id":"Q3792480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1096695314332e86b3b2747802c70b7fa4b9378b","datavalue":{"value":{"amount":"+0.8307070136070251","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":"Q1803680$D50BB1D6-BE6B-472C-AD7C-7B9DBFA9DDCC","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":"c7876e6fb06774cfdac88dde692f624fe01e2320","datavalue":{"value":{"amount":"+0.8307010531425476","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":"Q1803680$65A2E7DE-7A56-4CAC-9319-DBC6B70F28A1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A class of generalized greedy algorithms for the multi-knapsack problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_class_of_generalized_greedy_algorithms_for_the_multi-knapsack_problem"}}}}}