{"entities":{"Q1084863":{"pageid":1095615,"ns":120,"title":"Item:Q1084863","lastrevid":66895761,"modified":"2026-04-12T13:35:01Z","type":"item","id":"Q1084863","labels":{"en":{"language":"en","value":"Parallel approximation schemes for subset sum and knapsack problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3980482"}},"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":"Q1084863$366F7B85-397D-4C18-A9AD-F07D21E0845C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8f9576c13e0775d208178737c778b4604cdd4226","datavalue":{"value":{"text":"Parallel approximation schemes for subset sum and knapsack problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084863$8C631A2E-6ADF-43E8-9F97-3627045A9D7C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"03f3f62860f78e8a1947a824a878bd8596be842e","datavalue":{"value":"0606.68037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084863$0549259A-8FAD-4160-B832-17C8B4F63812","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dba86bc76877a8c53e810e07d6da64b199530358","datavalue":{"value":"10.1007/BF00292111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084863$02BDDEC2-62FB-4325-BA57-B3CAB53B0FBE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"64aadffbf26b62a00c16b5de77347396368c08cb","datavalue":{"value":{"entity-type":"item","numeric-id":294853,"id":"Q294853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$D55CFD27-5BA6-4D08-9198-995D863614D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"557610380305a380a1bcff327e0ca37178c3b5d0","datavalue":{"value":{"entity-type":"item","numeric-id":913511,"id":"Q913511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$5D8F39BD-9E27-4672-81E2-930527F43C00","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$9E3F8D97-EFFE-4E6B-A2B5-BD2A76E10E14","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1084863$346D0C84-D706-4B3F-B385-BF4CF8A205EC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"396055f78718e2adc4de4259369b536f22adb870","datavalue":{"value":"This paper presents parallel approximation schemes for the Subset Sum, 0- 1 Knapsack, and several other optimization problems. These algorithms offer a three-way trade-off among parallel time, the accuracy of the solution and the number of processors used. The maximum numbers of processors which can be usefully employed depend on n (the size of the input), and the accuracy requirement \\(\\epsilon\\). The parallel running times of the algorithms are polynomial in both log n and log(1/\\(\\epsilon)\\) when enough processors are used.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084863$CA841689-0A09-4247-9554-DDBC3648E86E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084863$8021AD06-1913-4989-A077-15320ACDEB14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084863$119B666E-4D1B-4427-8216-DC937861D173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084863$699B165E-5D95-4300-8000-6ED0B13354D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6a2e990bb2791a7301511acbfdaf2b2b2f430695","datavalue":{"value":"3980482","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084863$45BB78F5-F0BF-41CD-B8B9-EA212CC35CC6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a59b1493a3dfce77efe9c02f17396ec193aeaaf0","datavalue":{"value":"optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084863$ECFC00B4-9999-4FE1-A75D-05BA52BE8528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ca76aeaeac34f2599aeb993628873b067ed5308","datavalue":{"value":"maximum numbers of processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084863$DE8D00FF-BBFA-4B01-8141-0FDB8F8FF4CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"415b125c9cc76fcbd4b0e1f1dee1feccedefbf30","datavalue":{"value":"parallel running times","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084863$B2AE5261-39AC-4116-BBD7-745186F8B5AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084863$E250BA0A-9436-4A11-AEF7-B7472340E9CE","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":"Q1084863$D74C450C-ACC1-4E12-AAA4-B208E128CBD3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$DE88B858-FE68-4EFB-90DF-CB85C758E7A0","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":"Q1084863$E7E39134-225C-4327-A765-D7A5EF1443E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7710ffeeada2d9f282912589b152a6f3f13537aa","datavalue":{"value":{"entity-type":"item","numeric-id":3892056,"id":"Q3892056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$3995E411-49BD-498E-B9B4-0E3976325D1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c29444d1f0ddc8881b23b4a617e80310d2439ef8","datavalue":{"value":{"entity-type":"item","numeric-id":3907409,"id":"Q3907409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$31CF89BB-B72C-43A3-B63C-98D06EEEE12D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4b61211cac35171479d60a255285271d34d6b6e","datavalue":{"value":{"entity-type":"item","numeric-id":3050129,"id":"Q3050129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$8DCE1562-E1AC-488C-8FE4-B34E184E6DE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89737476846006649ef2e6d7db8390636ed69c75","datavalue":{"value":{"entity-type":"item","numeric-id":3898034,"id":"Q3898034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$373C1DEF-CE8A-42A5-BD27-1E0A6700C3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33e8a7ecbe695332ed12405b42bedc2893b98ce3","datavalue":{"value":{"entity-type":"item","numeric-id":4095869,"id":"Q4095869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$6259CAFF-07E8-4D8B-A707-2D26D83CB19D","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":"Q1084863$132415B4-7264-4D01-9D56-06742494BCA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"219f079f86ae987e344c3f57909db63f9a3e57cd","datavalue":{"value":{"entity-type":"item","numeric-id":1158970,"id":"Q1158970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$B6C89197-D70F-4A5A-ABBD-A041606A2297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d06b965cddff29eeda9bd63c3893117b299d7d10","datavalue":{"value":{"entity-type":"item","numeric-id":1084863,"id":"Q1084863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$8C4A11D4-B4C1-47D9-A918-71C6272775F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4f71afc6443c09db232af8245076ba93e72fb1b","datavalue":{"value":{"entity-type":"item","numeric-id":4091444,"id":"Q4091444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$F91A8812-ED1E-431B-99FA-FA5208D9A694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd8523119cae1e95195a813155916ad1fdd1ffaa","datavalue":{"value":{"entity-type":"item","numeric-id":4168785,"id":"Q4168785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084863$21249975-6BAD-4975-A4A7-76B0FC077FBE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5ad156f06836725c0735d7ed1712356f829312d","datavalue":{"value":{"entity-type":"item","numeric-id":757041,"id":"Q757041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdac3ba59e17f5d5c138c7e581a4c97c9bd94518","datavalue":{"value":{"amount":"+0.8782769441604614","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":"Q1084863$2B71E63B-03A7-40A7-9446-C0F746B8401B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"862f706aa938535cd3f3e9271eedd4fa49f3f706","datavalue":{"value":{"entity-type":"item","numeric-id":852950,"id":"Q852950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"964bb6b6e0939243388b812c627331cdc3bb1fb9","datavalue":{"value":{"amount":"+0.8503857851028442","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":"Q1084863$67A90065-66EE-4C58-959F-68EF3D16420B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49d0fdf9f1f2253ee2871f992b30438f89dafaf7","datavalue":{"value":{"entity-type":"item","numeric-id":4313818,"id":"Q4313818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16e9767367ee5d86d1be4b152cc9877bb3b9e131","datavalue":{"value":{"amount":"+0.8501706123352051","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":"Q1084863$79B207E9-E303-45BA-8A87-CDCBD9839357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c66a3da8c23700a7ba9c0874c3ef39fa11735461","datavalue":{"value":{"entity-type":"item","numeric-id":3774941,"id":"Q3774941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59f416a91eb2d14e7f2abda4330711efb989848e","datavalue":{"value":{"amount":"+0.8493144512176514","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":"Q1084863$2CCBA313-E446-4F25-900D-41F235333CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"698429bc6a48344ef3eccf4c2f36b3b7250093a2","datavalue":{"value":{"entity-type":"item","numeric-id":4370212,"id":"Q4370212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"382499215eef4de9ba8968b52db10ca90abbdff2","datavalue":{"value":{"amount":"+0.8460065126419067","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":"Q1084863$231D839D-0E40-4C5A-A70D-129CC0B2C554","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel approximation schemes for subset sum and knapsack problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel_approximation_schemes_for_subset_sum_and_knapsack_problems"}}}}}