{"entities":{"Q1811628":{"pageid":1822370,"ns":120,"title":"Item:Q1811628","lastrevid":73383039,"modified":"2026-04-14T15:42:44Z","type":"item","id":"Q1811628","labels":{"en":{"language":"en","value":"Average-case analysis of a greedy algorithm for the 0/1 knapsack problem."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1929385"}},"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":"Q1811628$8760AA02-C966-4874-9004-A364B99E4EF4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8f2ecb1a75945f44ae3d2947454cc3dbbbdbb8f8","datavalue":{"value":{"text":"Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1811628$947960BE-3843-4711-B16F-5B23E2C34AAA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d350af19c490bfdf57b3493e171b922aaeca4c09","datavalue":{"value":"1064.90026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811628$0EE8060A-D6BF-4C5A-9078-4B82F67ACB31","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c8d6e9669cf670792e87b5c52816ccfd4c90c3c","datavalue":{"value":"10.1016/S0167-6377(02)00222-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811628$268E9E21-0721-4A53-B12C-35CE0ED71FF5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0ac6ee42a687cd71f3c7c9eb7682358fd0c7068","datavalue":{"value":{"entity-type":"item","numeric-id":195459,"id":"Q195459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811628$BBBF4F09-340C-444D-88AE-F4C2797E3F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4af00457c53c070f202253e50a66260bb73f5ba","datavalue":{"value":{"entity-type":"item","numeric-id":210310,"id":"Q210310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811628$A57DEEC2-E71D-4E04-A882-40228872B581","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":"Q1811628$0E6E9349-060E-42CB-AA93-8DE84922CC0E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b0a79be519cf2c70225fbf164067e791560614d","datavalue":{"value":{"time":"+2003-06-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1811628$DB64967C-A773-492C-A4A8-9CFDCFDB6B5D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811628$89DA0143-BE75-4E57-8B36-9D189F04A8F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811628$CBF18C1A-C8F6-4D87-80FB-564FD39097CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811628$F028945A-6ACA-4858-8453-DFFEBD18BEE5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d8b25aa8f12bb72aef70770aaa8da3b005e1952f","datavalue":{"value":"1929385","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811628$140460D0-CDCE-4917-8A90-E7B52308B614","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69eda5d7797ea77a21183d25cb52b1a8f29b7316","datavalue":{"value":"0/1 knapsack","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811628$C17D09BC-3A5C-4FFD-AD71-4DA715403EC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811628$C20ECB7D-B1D4-4BE0-9236-0D316287525D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811628$3EEA0ED1-EBDC-4A12-8DD8-EE8C2EE53587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811628$8CFD3FC0-23D1-4EBB-A852-D399E482C0AC","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":"Q1811628$C80BE30A-2E32-4A13-8504-21A0BD88EF7D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac89c6d52a7b4808087c3b5979aefa227f2f15c6","datavalue":{"value":{"entity-type":"item","numeric-id":5560061,"id":"Q5560061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811628$1334B759-E6DD-4FA1-924B-62ED6BD49D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d598930b538b7c0a574bd7ef5804304bafd2132","datavalue":{"value":{"entity-type":"item","numeric-id":3832316,"id":"Q3832316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811628$9959104B-5E0F-4BF1-BA64-6B9A63BB583C","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":"Q1811628$D1AE56B3-A3F7-4A0C-8BF6-BED42A8DFF21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7a3222f0ee1cf2830bf52429f4c4026e71c278e","datavalue":{"value":{"entity-type":"item","numeric-id":1181902,"id":"Q1181902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811628$F5CE1C01-66A9-4FEC-BD4C-D7B292546E4B","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":"Q1811628$3B075E03-7C64-4DA4-B76A-266AED364F7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d738e694de5fb590baa9d0597ed26f0c2b51fbc6","datavalue":{"value":{"entity-type":"item","numeric-id":4076577,"id":"Q4076577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811628$2858F5FC-D7DD-4F48-8D87-360BAFF95616","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":"Q1811628$61E42258-9D46-4546-878A-1468CEA9B526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e5e11588b3956984b6f36168223f68811c36bab","datavalue":{"value":{"entity-type":"item","numeric-id":4225866,"id":"Q4225866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811628$819CF538-D7A1-422B-9751-1A99C15A44D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"186faded9c2aba9d5423c324a8cedcc4e8091a7c","datavalue":{"value":{"entity-type":"item","numeric-id":3783565,"id":"Q3783565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811628$0FF8362D-CCF6-4EE0-AFA3-035BD0586FEF","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":"Q1811628$86F40650-31D7-40FC-B663-3188D87811A2","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":"Q1811628$168F9C9A-0C8E-4423-A014-C57554B6546B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fe07d7ada9c4d737fc0974226fb8167464f14710","datavalue":{"value":"https://doi.org/10.1016/s0167-6377(02)00222-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1811628$3F64EB63-86F3-40C0-8D1C-6E1A85D4D799","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7376a88276336e0f2b714bf63bfe4caa57e424ac","datavalue":{"value":"W2041429356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811628$D3513353-8C6E-4531-85F5-780AE5825A08","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":"e2c00c7f2cc1077b4a3d1dd283ee1fa312a35061","datavalue":{"value":{"amount":"+0.8410870432853699","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":"Q1811628$E211962A-3120-41C1-A886-900AE1E8C9BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"574c0a7a5a139512012c19815aa636df9e23f6a6","datavalue":{"value":{"entity-type":"item","numeric-id":4225866,"id":"Q4225866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5219d64f8fc5769021fed752c3bfbeaa2129942a","datavalue":{"value":{"amount":"+0.8408640027046204","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":"Q1811628$9D46E31E-155D-49AE-B2B4-500F188A1987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa83443b9a1aa4d056fed51c2af692a1d496a242","datavalue":{"value":{"entity-type":"item","numeric-id":4886047,"id":"Q4886047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c18064592f54e800ecbee736c58d65a2e1c53a5","datavalue":{"value":{"amount":"+0.8404526710510254","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":"Q1811628$D0E4DF1E-05E0-461C-B4F4-3130BD6824D1","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":"7de89c660a310487a3aeb0ec8b5ce657b9eeb1e4","datavalue":{"value":{"amount":"+0.8403069972991943","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":"Q1811628$9FDE2256-64EA-4234-B02E-CD57629AD7DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d8f205579eed502bc3f508ffa06d721d37f8d25","datavalue":{"value":{"entity-type":"item","numeric-id":3343773,"id":"Q3343773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a2a49c3d4f35b6b25a8f47428de6dec9488e917","datavalue":{"value":{"amount":"+0.8360792994499207","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":"Q1811628$E6555247-E0A3-4395-B1DB-568A468F16D3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Average-case_analysis_of_a_greedy_algorithm_for_the_0/1_knapsack_problem."}}}}}