{"entities":{"Q789319":{"pageid":791167,"ns":120,"title":"Item:Q789319","lastrevid":64351932,"modified":"2026-04-11T19:16:56Z","type":"item","id":"Q789319","labels":{"en":{"language":"en","value":"Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3845351"}},"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":"Q789319$9E192B2A-1347-4E43-B1D2-7EEC3F0120D8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2a63e9da3e0073cef9ba460dbf43eae7add7f4bd","datavalue":{"value":{"text":"Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q789319$AD60D36C-995D-4270-A8A4-E0B123A2D89E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b70394f50ea3e4aa4683c50906c64ed5069a47c","datavalue":{"value":"0532.90075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789319$CC6FDF52-7E11-42D0-88F5-FFD8A75F82E2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe36bb6626a81242214ed3d448a5035a481a4a99","datavalue":{"value":"10.1016/0377-2217(84)90053-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789319$70F6DC78-84E4-41D7-989B-478D7E8C3B9E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"547b614a1ea25c340129ea4bb81c9956c3021424","datavalue":{"value":{"entity-type":"item","numeric-id":673731,"id":"Q673731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$60A3F8E6-5B2C-4947-AE94-75F3D08BE1D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$B382E166-B45C-49C3-917C-5DDC4A072E72","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$2DFB80D5-3F53-44AC-86C8-741DF81A4EDB","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":"Q789319$54A5CB24-99B9-4A39-B58D-3D2FAFD3C0CD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"326f9a6c9187b80c867c12843dd9472bc9502bdc","datavalue":{"value":"This paper is concerned with the m-dimensional 0-1 knapsack problem:  \\[  (1.1)\\quad Maximise\\quad z=\\sum^{n}_{j=1}c_ jx_ j,  \\]   \\[  subject\\quad to\\quad \\sum^{n}_{j=1}a_{ij}x_ j\\leq b_ i,\\quad 0\\leq x_ j\\leq 1,\\quad x_ j\\quad integer,\\quad j=1,...,n;\\quad i=1,...,m,  \\]  where for all i, j, \\(a_{ij}\\geq 0\\), \\(b_ i\\), \\(c_ j>0\\). m is considered to be a fixed constant. The problem is known to be NP- hard even when \\(m=1\\) and so there is interest in finding heuristics which work in polynomial time (polynomial in the input length) and have a guaranteed accuracy. Given \\(\\epsilon>0\\) we say that an algorithm is an \\(\\epsilon\\)-approximation algorithm if it always produces a solution \\(\\hat x\\) with objective value \\(\\hat z\\) that satisfies  \\[  (1.2)\\quad z^*-\\hat z\\leq \\epsilon z^*  \\]  where \\(z^*\\) is the maximum value of z in (1.1). The aim of this paper is two-fold. In Section 2 we present a polynomial approximation scheme for problem (1.1), i.e. for each \\(\\epsilon>0\\) we describe an algorithm \\(A_{\\epsilon}\\), which is an \\(\\epsilon\\)- approximation algorithm and runs in time polynomial in the length of the input description of (1.1). In Section 3 we conduct a probabilistic analysis of this problem and obtain reasonable tight bounds for the asymptotic behaviour of the objective value \\(z^*\\). A simple consequence of this analysis is that with probability \\(\\to 1\\) as \\(n\\to \\infty\\) the solution obtained by rounding down the solution to the linear program (1.1) satisfies (1.2) with \\(\\epsilon =n^{-a}\\) provided \\(a<1/(m+1)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q789319$C0F07C10-2C85-4697-98A0-44DAF06744F4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789319$7B17CB7C-A585-4CE8-B979-6626E6FB58DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789319$6B0F9072-DC8F-410C-A920-FF582C7B585B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789319$44ED5DC4-56A3-43EF-A6FF-AF2044B2CE2F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28af25a690505d10b7627529f3fb99ed8acb8559","datavalue":{"value":"3845351","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789319$CDA3DC6C-1291-49F3-B22C-E32AD71EA353","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c27e3e5228254e1f12d701b97ae7a76bdc103c7a","datavalue":{"value":"dual simplex algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q789319$CAF431E2-0DE0-4813-86EC-63B936CB325A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7983236bb6708c2a20748d2d7172e6d07222a1f","datavalue":{"value":"epsilon-approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q789319$3F13FF01-05F0-45B3-8681-DA6B20E64F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8fd630b5bd4e3845db3a791b5fe178eea3311d1a","datavalue":{"value":"m-dimensional 0- 1 knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q789319$21096FD9-7CCD-4894-8F8F-A3662D310645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10856616c8697c996715954944e42bbfb34eb3f8","datavalue":{"value":"polynomial approximation scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q789319$D32A261E-F9DA-4EC3-B2E0-5EFCF6A36605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q789319$CAC70932-E0C0-40EA-B58E-23217F3400DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6402c22d477fcda411db02b5c3a1f2fe19f1b058","datavalue":{"value":"tight bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q789319$37FF21C5-9660-4560-8D80-7B121F989CEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8c9573404f466fc73de1e6d423407b5543ac068","datavalue":{"value":"asymptotic behaviour","type":"string"},"datatype":"string"},"type":"statement","id":"Q789319$8D45D4BB-929F-44F7-96C1-35E5B9E1A9A1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5f27aa8f7a7153c2499cf13ced6841b8bfa6c759","datavalue":{"value":"Q57401633","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789319$EC38ABD2-5115-4962-9266-0805EF3BFA35","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":"Q789319$6CC6DCA0-F551-421B-9103-42D0681EB0A2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d66d8e8f71d31e4df53ff4c4923748afdce9c2e","datavalue":{"value":"https://doi.org/10.1016/0377-2217(84)90053-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q789319$156F6CB1-2EBF-4553-9A40-9487C86DE8FC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e911073768d1120da4b166afe7a494c1e3e57800","datavalue":{"value":"W2055037276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789319$E2EC647E-AD23-47A0-BFB2-D7A835672DBA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$228DA62E-B4D9-4C64-A94D-6AD006E1A42E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1abd810edd219852725b067482cec49006a7192","datavalue":{"value":{"entity-type":"item","numeric-id":1238705,"id":"Q1238705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$068D5739-021C-4339-9946-9E070CCF2531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$6A23129A-B8AE-46CC-A459-6654F5CC3709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b206f22830573dd4a250b8325d03e6b36767da6e","datavalue":{"value":{"entity-type":"item","numeric-id":3914757,"id":"Q3914757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$FF2BA394-5DF7-4C52-8363-7C164D25AE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65d73ae8ce50631a13a2e25599a048bc2eda73","datavalue":{"value":{"entity-type":"item","numeric-id":4158479,"id":"Q4158479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$9F4E6A19-B241-4C8F-B8E3-99FA22A99B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b916828114586c907ab9703174b17d58bf1c2d1","datavalue":{"value":{"entity-type":"item","numeric-id":4114965,"id":"Q4114965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$3A4349D1-DD5C-4905-98D3-D061E7A363D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$A13F09E7-0A93-494B-8EA9-14A4E79C692E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97236fbeb6b6b2bba840114a8ba2f0448b9619f9","datavalue":{"value":{"entity-type":"item","numeric-id":4197641,"id":"Q4197641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$D8593951-75EC-4604-9EDE-F78A3F116F47","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":"Q789319$78C23970-A121-481E-A1B0-39C43733801D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bfb71032cace7d4b860d3bb0857ac160eb94fd6","datavalue":{"value":{"entity-type":"item","numeric-id":4171868,"id":"Q4171868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$0CD2623F-1E3A-45B3-9AB8-1004380F924F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60b4dd1e71e3ee7fffaa8703001d4660e04e8ff7","datavalue":{"value":{"entity-type":"item","numeric-id":4849260,"id":"Q4849260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$D035FB09-4F04-4C40-A4D0-CD84FA4D33BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4bb130c72c83098fac2d21981e689cc6dd310ba","datavalue":{"value":{"entity-type":"item","numeric-id":4136930,"id":"Q4136930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$6AC55901-DFCA-4674-86DA-90242F2CB3A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12fbfd3a15b60e4867fc646beb8a6203bfb16e20","datavalue":{"value":{"entity-type":"item","numeric-id":5534682,"id":"Q5534682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789319$21726A85-51AD-4E75-BD2D-93E77B09477F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e66c648ace984452ce6ac55662c5f3b78287aea","datavalue":{"value":{"entity-type":"item","numeric-id":5240419,"id":"Q5240419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f93d70e223af3c713057202246ca6b92fbd63780","datavalue":{"value":{"amount":"+0.9263197","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":"Q789319$8191AFF8-0903-461C-B9AE-E6194D9FA3A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6fe89856f4fa9cfd23de95d211425283db8171a","datavalue":{"value":{"entity-type":"item","numeric-id":817185,"id":"Q817185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b1ed6c0f408c876cca9333a49d64a610a149b8d","datavalue":{"value":{"amount":"+0.9222722","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":"Q789319$A00B97EF-7CFF-4F47-BD78-E79FC64AAFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00b88e6c4a6cc9d3a74133c7ddeba2805593f940","datavalue":{"value":{"entity-type":"item","numeric-id":3780001,"id":"Q3780001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd759fae54142e802ab08c3290bcbb3bc6cc932e","datavalue":{"value":{"amount":"+0.9199472","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":"Q789319$B8C864EB-584D-486F-9457-BB8950D316D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcc8a539e7d28a8a92e4a4547d3b4f9ce8191924","datavalue":{"value":{"entity-type":"item","numeric-id":489742,"id":"Q489742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4a0124952a40bd493ec2bdae43b3fe701508c92","datavalue":{"value":{"amount":"+0.9145298","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":"Q789319$D1CAD025-8D84-4578-B1FC-03CA2F2D7317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"192049b49f008d776b93a01866b3875e6ea18f4e","datavalue":{"value":{"entity-type":"item","numeric-id":1977259,"id":"Q1977259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dc0e57169613f8c437bb7bce4ab0e40139aac96","datavalue":{"value":{"amount":"+0.9141051","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":"Q789319$54CDE3CD-8ADA-492E-8B2A-5FD2DD9C8CC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccf7fb5e7a585976ccdb68409f48744c027ef011","datavalue":{"value":{"entity-type":"item","numeric-id":3718485,"id":"Q3718485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e4511b7e74df24a71e7d7aeed04c63847dd1b04","datavalue":{"value":{"amount":"+0.9118101","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":"Q789319$37BDB5B1-D5DA-473E-902E-0B39248A6302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f42e231dfd20bafcece36b154170501e7152aa7f","datavalue":{"value":{"entity-type":"item","numeric-id":2282074,"id":"Q2282074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52ac8640f0e73187746a6d74afc270caa77455fb","datavalue":{"value":{"amount":"+0.90857404","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":"Q789319$9F59FA3A-4D65-42C3-A34E-87E3FA81BA32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"267fd4e0d0f2cfb8ea0fe5314acc5d43dccf395a","datavalue":{"value":{"entity-type":"item","numeric-id":699820,"id":"Q699820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"647e156df18063d8887b24cfb80b2a54a598f6cb","datavalue":{"value":{"amount":"+0.9059533","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":"Q789319$DCB0DDEE-6AA5-4A78-AF65-28A335EC1991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"473189a29680c2149bea2c9597d6dbe31dc44ee0","datavalue":{"value":{"entity-type":"item","numeric-id":1569936,"id":"Q1569936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02d96d840d34a218bb9a9537a189ce2ebcb5c820","datavalue":{"value":{"amount":"+0.9035863","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":"Q789319$CEC17537-4E2B-43C4-9C97-89580538A021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d064dda10a9b0e6ed509db9f2cde607ea70804c6","datavalue":{"value":{"entity-type":"item","numeric-id":506160,"id":"Q506160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42bc20980b599238da64df726f2d17244d893451","datavalue":{"value":{"amount":"+0.90311146","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":"Q789319$17E79B5F-BC37-4DAD-99A1-F01768E31712","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithms_for_the_m-dimensional_0-1_knapsack_problem:_Worst-case_and_probabilistic_analyses"}}}}}