{"entities":{"Q913659":{"pageid":915507,"ns":120,"title":"Item:Q913659","lastrevid":49380229,"modified":"2026-01-07T01:43:45Z","type":"item","id":"Q913659","labels":{"en":{"language":"en","value":"An exact algorithm for large unbounded knapsack problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4147864"}},"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":"Q913659$99C4F97C-B04B-4357-8057-A4B51032CA21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f3f3cafd336f9c3c4f5c3a7bbc2d0e8832928d74","datavalue":{"value":{"text":"An exact algorithm for large unbounded knapsack problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q913659$79782C9B-6692-428E-8A1C-A637C1BB0350","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61e80d5bb2d896deb86486b2f93a31ad56839b6a","datavalue":{"value":"0699.90076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913659$6B70BD18-0417-4408-BB96-7C993D0B713F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d494a31d240a2aff97afd24b0654e1a450f917b","datavalue":{"value":"10.1016/0167-6377(90)90035-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913659$F36B4717-C0FE-4F59-A750-C9E1C2EE8C52","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03fd981d5df261cfa2446e7ed1d18dfa2af040b2","datavalue":{"value":{"entity-type":"item","numeric-id":193678,"id":"Q193678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$F1C5D35E-EB2B-4343-9A0A-36A992DF31CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4f4e50ab5ff3e3fa6e97103b12136833b436f53","datavalue":{"value":{"entity-type":"item","numeric-id":181212,"id":"Q181212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$2A9BAC23-D1A2-4DA6-B0E3-68202CA67D62","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$4116730A-63CD-4FD2-8810-E0773956F7EE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q913659$DFDB8B8F-0387-418E-AC7F-49F84773D645","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"539bc26fa47855b6a67d7b8b4b1eb0048e422e32","datavalue":{"value":"The authors give upper bounds for the objective function of the problem  \\[  \\max \\sum p_ jx_ j,\\text{ subject to }\\sum w_ jx_ j\\leq c,  \\]  where \\(x_ j\\geq 0\\) and integer. The bounds are obtained by careful use of the three largest ratios \\(p_ j/w_ j\\). A branch and bound algorithm based on earlier results of the authors [Adv. Oper. Res., Proc. 2nd Eur. Congr., Stockholm 1976, 295-301 (1977; Zbl 0372.90094)] takes into accunt the fact that in the most cases only a small subset of the variables are nonzero in the optimal solution. Computational experiments with correlated and uncorrelated uniformly random data show the high efficiency of the presented method, for example, the average running time for problems with 250.000 variables is about 66 seconds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q913659$D5B04D24-F4DD-45E1-A601-38557810CBBA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913659$834BEE5B-AB7E-46CB-8AAC-860FB697C16E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e038e5e16128fe63d90643b4c4804d63f3db1339","datavalue":{"value":"90C06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913659$74989DD3-30EA-4BAE-A18A-441F7B1B4A38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913659$E84A569A-03DB-4B71-BEAD-E90E9CE2B20D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a4e814aa49e1189adbd1bf4e964c8779abf0194","datavalue":{"value":"4147864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913659$430E355A-E7E0-482B-AF0E-9F29A62A0F2E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b054bbd1ef16f604df0f61144322893e5b9a2a9","datavalue":{"value":"upper bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q913659$D90950B2-4E99-442C-AB9F-1C3E780BA63D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfbcaaf2f1a9ac15831ae6c3d4dd30c7f84e33bb","datavalue":{"value":"branch and bound algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q913659$86814519-18B5-4F94-A5E1-8C68B85D2791","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":"Q913659$BA7C64D5-D99E-42B6-A2D3-BF5AFA788780","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6721a7f1e956a102fed0cb4ef8b39fddf626ebed","datavalue":{"value":"https://doi.org/10.1016/0167-6377(90)90035-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q913659$69418BE5-9247-46D2-99C6-94D7FFF759A3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fd76f0fa3fe043ed295108e3ae2a127d9ac021b4","datavalue":{"value":"W2127967088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913659$10D060E5-B5D4-4D1D-91C2-166BC33FD2F0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d45fa841a6a5a6e49fe7dc5b973e71a214489c6","datavalue":{"value":{"entity-type":"item","numeric-id":3896840,"id":"Q3896840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$B9BD9C0B-4D2D-4528-A903-2B8CC3FF0494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22d5f54751a36c5174a4e3a9932fbe1a544217a6","datavalue":{"value":{"entity-type":"item","numeric-id":5378625,"id":"Q5378625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$608516D4-DEBA-45A0-B185-3F291F82270F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f1a58dd56513555cdf1d0c1ca60995e61dc3549","datavalue":{"value":{"entity-type":"item","numeric-id":5591244,"id":"Q5591244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$576BEEAD-0422-4DF5-B493-13CB9A9AC78E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"552127697b54f48dfe1e9d47768fe1f179805934","datavalue":{"value":{"entity-type":"item","numeric-id":1156694,"id":"Q1156694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$B39C5E3A-D749-4055-A1AF-85DEADDA0CE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa74c0bb2c71d8d24f83c953c7f1811531f8473b","datavalue":{"value":{"entity-type":"item","numeric-id":3214706,"id":"Q3214706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$53604EB8-1ADE-4ED4-9F28-514A51E79EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02e5846a8a2b23e50649c744d199c26a3ee1cc7","datavalue":{"value":{"entity-type":"item","numeric-id":5328572,"id":"Q5328572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$C38ABAFC-D44C-45A3-9ACA-2AC6E34076F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"444ef82be7aa085e4e525b91df0d015c6d506b67","datavalue":{"value":{"entity-type":"item","numeric-id":5560786,"id":"Q5560786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$6080B931-C072-4D20-B149-08283B020FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d210f473c7e5129745b162cad32ea74f1c7af9d2","datavalue":{"value":{"entity-type":"item","numeric-id":1137512,"id":"Q1137512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$9AF25D00-5602-41BA-831A-112181FD8102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4facdcdfa11164192d8ebfbbb7464026ef529df","datavalue":{"value":{"entity-type":"item","numeric-id":1082265,"id":"Q1082265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$023B8AC2-74FF-44A3-B078-8E4E53D34362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1611b9e99c2887921bb4687cfd5ca63580eed960","datavalue":{"value":{"entity-type":"item","numeric-id":4114964,"id":"Q4114964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$86D17062-756F-4225-B2EE-A9D1EB01B9DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03f1ddaba8285217bb41a356c810dd9d4f0f25b5","datavalue":{"value":{"entity-type":"item","numeric-id":5595961,"id":"Q5595961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$CD99DBD1-A10B-4E34-A23B-A595A35B0582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e22334a5019e7726da90389342137c92fb3bb240","datavalue":{"value":{"entity-type":"item","numeric-id":3858024,"id":"Q3858024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$DCD8D5FD-392D-41CB-B253-6AB5EB544C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaf1022db4a42ecb807eebe5be57a911b60556e4","datavalue":{"value":{"entity-type":"item","numeric-id":4062195,"id":"Q4062195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$6EF39451-4748-4466-AEEA-DFB24DDFFB59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b12f577ecb17608fcd09e60751a87188192c6636","datavalue":{"value":{"entity-type":"item","numeric-id":1245074,"id":"Q1245074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$22898591-3F61-4717-91C5-B5881281F729","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63d676aaa20be6eda2f7ce9b6741ff084de47abe","datavalue":{"value":{"entity-type":"item","numeric-id":4149228,"id":"Q4149228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$8FC88869-B736-48A1-B857-078A8AC97A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d3ad6fbc9d544f63cef170de23284269dffa20","datavalue":{"value":{"entity-type":"item","numeric-id":3751378,"id":"Q3751378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$4C4A415B-C9A8-4107-B246-7AB94F9A1CC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8696fe5bb133fa030240ed4293d41502d6e976b","datavalue":{"value":{"entity-type":"item","numeric-id":3789335,"id":"Q3789335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$45C7D8EB-A37C-4EF6-BB7A-60240054C18D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d834b2f061333007e84559a210df1dabd1b7c737","datavalue":{"value":{"entity-type":"item","numeric-id":3993418,"id":"Q3993418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913659$4F086841-B3AB-49D8-A82A-86E1EA6A3CF2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d11efbcb79f2ae71ffa1ed42bc8887d091fba3e6","datavalue":{"value":{"entity-type":"item","numeric-id":4661050,"id":"Q4661050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"759773efff41d4157e83577e368b0dc116db8267","datavalue":{"value":{"amount":"+0.8595923781394958","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":"Q913659$6D275D95-DD15-4721-846C-78A128FB3271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37bc28041ea835c496417ae99c4f8e8bfd603f57","datavalue":{"value":{"entity-type":"item","numeric-id":3789335,"id":"Q3789335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c93edf0119d18038755f2e2adf5f31d94e84d5f4","datavalue":{"value":{"amount":"+0.8385634422302246","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":"Q913659$C6B99B51-A195-477D-A130-87F60A8CE15B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e175a613ea5c398d7b05f14141a07629d4cf016d","datavalue":{"value":{"entity-type":"item","numeric-id":2971610,"id":"Q2971610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d4977b599936dbc9c85333fd2e18e8202181175","datavalue":{"value":{"amount":"+0.8355050086975098","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":"Q913659$D782E5D2-8BE5-4FC7-A8BD-59ACEF5D1A84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63924abf92f1325301764d2fa8d1f354a8931d84","datavalue":{"value":{"entity-type":"item","numeric-id":3116647,"id":"Q3116647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cecc65752fea5856d8f5d3f71380fc66a626712","datavalue":{"value":{"amount":"+0.8321714997291565","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":"Q913659$2A4E0FFC-4B0F-4042-BF39-7B42960F5AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31713d51c68c0b3b73c4098d780bb47912d2a596","datavalue":{"value":{"entity-type":"item","numeric-id":2735077,"id":"Q2735077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5bc11c12af997cee56094daf1f8ac596681a1de","datavalue":{"value":{"amount":"+0.8266730904579163","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":"Q913659$2E89D490-AB24-48A4-A29C-ECFFA769D885","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:913659","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:913659"}}}}}