{"entities":{"Q1853236":{"pageid":1863978,"ns":120,"title":"Item:Q1853236","lastrevid":73041888,"modified":"2026-04-14T09:42:57Z","type":"item","id":"Q1853236","labels":{"en":{"language":"en","value":"Comments on parallel algorithms for the knapsack problem."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856551"}},"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":"Q1853236$F272CFA2-617E-4DBE-B161-16AD6FD3DEE4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0690fa8410805ab4a576d09ecdb3405dbf2570e7","datavalue":{"value":{"text":"Comments on parallel algorithms for the knapsack problem.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853236$72CF1DD0-FF5A-4B1A-A6F7-7A680B15A291","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"825741530c0a1c8ce2d275f04283a17e8406a6c6","datavalue":{"value":"1052.68149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853236$67CDF22B-7335-4249-8F4D-863BDB31BA4A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c283b36a7d744e2f27fb012e977225ea2c1128a0","datavalue":{"value":"10.1016/S0167-8191(02)00150-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853236$1CA05245-77C5-4C77-80B8-4486940001DE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"568b40e7763c4af9974fcb62633b1b4bab701dc2","datavalue":{"value":{"entity-type":"item","numeric-id":275219,"id":"Q275219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853236$83958AC1-B7FD-41BF-B5F1-73ADE31A96E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f7870f3728a90c91078689f67cf8e789b894d3b","datavalue":{"value":{"entity-type":"item","numeric-id":228558,"id":"Q228558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853236$895A134D-E1FB-48FB-89F1-C321FE44F8A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d74146e4a51179e01c420dae915e57ee49a320b","datavalue":{"value":{"entity-type":"item","numeric-id":991071,"id":"Q991071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853236$D59C3B52-723F-468F-8DEA-94FA3BBB4968","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"eeac13f60c55bdb04ecb49274cc7b24a1688345d","datavalue":{"value":{"entity-type":"item","numeric-id":71527,"id":"Q71527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853236$6F7496F0-272F-4C7A-8EDA-DE9E0FF219BC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853236$4D1D9779-0854-4024-B681-A55596B1BD8D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd34c244e35729ce884124a23fb0e24c49dc26e1","datavalue":{"value":"\\textit{H. K.-C. Chang}, \\textit{J. J.-R. Chen} and \\textit{S. J. Shyu} [Parallel Comput. 20, 233--243 (1994)] introduced a parallel algorithm based on a shared memory SIMD architecture for the generation phase of the classic \\textit{E. Horowitz} and \\textit{S. Sahni} [J. Assoc. Comput. Mach. 21, 277--292 (1974; Zbl 0329.90046)] two-list serial algorithm for the knapsack problem. They claimed that their parallel generation phase could be accomplished in time \\(O((n/8)^{2})\\) and in space \\(O(2^{n/4})\\) with \\(O(2^{n/8})\\) processors. We prove that their results are not correct, i.e., that the suggested scheme time and space complexity should be bounded, instead, by \\(O(n2^{n/2})\\) and \\(O(2^{n/2}),\\) respectively. These results also invalidate the performance analysis of the more recent \\textit{D. R. Lou} and \\textit{C. C. Chang} [Parallel Comput. 22, 1985--1996 (1997; Zbl 0906.68079)] algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853236$AE88AF04-3E51-49C6-9391-B921E95BCAFA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853236$350C50FC-3688-427F-A078-36F63575C451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853236$46FAE9D3-DAC7-43C5-AF81-316E8384BD95","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7c9119f029e52cfdfd1dde2e1fd4d04d39534e3","datavalue":{"value":"1856551","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853236$D52EBC26-9321-4FFF-8AFC-7AFA6A4BE1A1","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":"Q1853236$F58E5A67-9D07-4BED-B86B-B42BA94C0A40","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b439838e54b7dcbd8646f85b7dfc086c85a6fb2a","datavalue":{"value":{"entity-type":"item","numeric-id":1392066,"id":"Q1392066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33fa6e49ddc98d3f57c8ed10eb71e599923c8361","datavalue":{"value":{"amount":"+0.8793466687202454","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":"Q1853236$180311E6-8E83-421D-9D27-2FED2D404B6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6bfa59b577ab1a11fb7526412febdcbb43a7e62","datavalue":{"value":{"entity-type":"item","numeric-id":4470890,"id":"Q4470890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fa3375a2a9bd42fd526fe8e5ca3f1ef9607e5f6","datavalue":{"value":{"amount":"+0.8751710653305054","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":"Q1853236$C14D5088-0F99-4862-8CE7-421AC40EDE07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6d54eed786a5de0a330c85afe8abc8d31e3de8f","datavalue":{"value":{"entity-type":"item","numeric-id":991072,"id":"Q991072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab246f297b7d871d78523f981690cdf726d6719f","datavalue":{"value":{"amount":"+0.8411032557487488","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":"Q1853236$0F2B39EF-8D9C-4E70-9BFC-9054947D19D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d99e94eab19e0de73ca25bb09918fc483c7548d1","datavalue":{"value":{"entity-type":"item","numeric-id":5469596,"id":"Q5469596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f31ad9c0ea417f6293467a5e305d7d3b840fd82","datavalue":{"value":{"amount":"+0.8255524039268494","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":"Q1853236$2975FC33-6374-465F-8C9B-64CD7763777D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e5a17fda487870862e3466aab4cc142df2ca6f8","datavalue":{"value":{"entity-type":"item","numeric-id":1919114,"id":"Q1919114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"906f55d4ddb76947214def45ae18ddd4eb228506","datavalue":{"value":{"amount":"+0.825309693813324","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":"Q1853236$02DF23C0-979D-4D41-92F1-8D233148FB6F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Comments on parallel algorithms for the knapsack problem.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Comments_on_parallel_algorithms_for_the_knapsack_problem."}}}}}