{"entities":{"Q2276878":{"pageid":2287621,"ns":120,"title":"Item:Q2276878","lastrevid":49477681,"modified":"2026-01-07T05:38:15Z","type":"item","id":"Q2276878","labels":{"en":{"language":"en","value":"On the solution of concave knapsack problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4193459"}},"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":"Q2276878$5ED16A97-8F4D-47C6-8F03-F31AB36A2CA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"821898d24c2996cf74f5695583ea767c58bf3b52","datavalue":{"value":{"text":"On the solution of concave knapsack problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2276878$9EBF24E2-2150-40FA-852E-544A045E0CC2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"26b419455c2ab6525e15a678db951b4b4a643203","datavalue":{"value":"0723.90059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2276878$B422995D-D6D5-42EE-8C02-4AEBD8573918","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"43c645009f1dcaa5bc3287fa339fa427ef560192","datavalue":{"value":"10.1007/BF01588800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2276878$58FD6802-752B-4541-8D8B-82752B07F087","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dda0c8c3f2551cc81d0834f72f696ff9dbc1485f","datavalue":{"value":{"entity-type":"item","numeric-id":233988,"id":"Q233988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$1C69B91B-223A-4842-8A8B-7AEEF1F98097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"19314e3717055044c35e04dfd4d786bc91a8affd","datavalue":{"value":{"entity-type":"item","numeric-id":687093,"id":"Q687093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$C0B3ED79-D01F-47BA-8FA2-267E88228554","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$EDAE6C91-F42C-4E8A-ADA1-D67C6E5CF48F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q2276878$602D2251-9BB1-4B21-9AB8-5D9F4474493E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4b54a202a1861eef0ff199225457482bbe79276b","datavalue":{"value":"Local minimizers of some special cases of concave knapsack problem (CKP)  \\[  \\min \\{\\sum^{n}_{i=1}q_ i(x_ i):\\;\\ell \\leq x\\leq u,\\quad \\sum^{n}_{i=1}a_ ix_ i=\\gamma \\},  \\]  where the functions \\(q_ i:\\) \\(R\\to R\\) are strictly concave differentiable functions, may provide upper bounds and can be good approximations to the solution of the 0-1 knapsack problem, considered in the form: Given n integers \\(a_ 1,a_ 2,...,a_ n\\), and an integer \\(\\gamma\\), determine if there is a subset \\(J\\subset \\{1,...,n\\}\\) such that \\(\\sum_{j\\in J}a_ j=\\gamma.\\)    Strict local minimizers of CKP are characterized and an algorithm for their computation is presented. The authors prove that the algorithm requires at most O(n log n) operations and \\(1+\\lceil \\log n\\rceil\\) evaluations of the function.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2276878$781A1B7B-941F-4ACC-992F-3AA9EEE85DC2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2276878$4BF97A54-4E59-4EB4-B211-7A068A98ED88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2276878$83A550FB-2E7D-457B-BF10-44157331F2F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2276878$4FCC29E0-2396-4281-966C-64374240D56A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2276878$7224A233-8B65-4DB6-9D56-1C859AE0F798","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"de5e0f70a0809c4dde8543147100413e7fdf18ee","datavalue":{"value":"4193459","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2276878$88B40045-2153-4AE8-A04A-F554ED3680BC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1896414e2c736fd254f64ae61addb608a816345","datavalue":{"value":"concave minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2276878$257D3F0B-EC5D-4C00-B5BC-6F1D4753F180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0941f297604d49f592f956e35591c7c203a942f","datavalue":{"value":"Local minimizers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2276878$3EDC3E25-86A2-416C-A1D0-5375807C5871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c40457ed1ef68a09ecc30056aa7fd6a46579c42e","datavalue":{"value":"concave knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2276878$93FE40C0-A499-4DBD-98FD-DEE142B87661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b18fbf4da4d18812aca4302e3ad936ca1c987b3a","datavalue":{"value":"0-1 knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2276878$FB0091FC-546C-4C80-A539-0566AF81A69F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2b972ef175b4299fdbfc53bb71881ff0c6d5f85c","datavalue":{"value":{"entity-type":"item","numeric-id":587047,"id":"Q587047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$743373C6-A5E2-4FB6-9C87-98535DD67988","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":"Q2276878$95C22D78-9DED-4D74-8F2F-B87F2E42D2B9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd522213c8f5f2bdfcfa7e22f5e736682ca63c6b","datavalue":{"value":{"entity-type":"item","numeric-id":797501,"id":"Q797501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$E73C806A-E89A-485D-8B7C-32D596BA09FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"883b7c7f820d0ed8ef95b12b822670ce30bf743c","datavalue":{"value":{"entity-type":"item","numeric-id":3787365,"id":"Q3787365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$768E0AE1-F299-4354-A9FF-35DF011124E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca82e75206fdcb32a935b78c020e1372222f41f9","datavalue":{"value":{"entity-type":"item","numeric-id":1134002,"id":"Q1134002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$F9A4805B-4518-42C0-81BB-519A962B7487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b797371b15b7531e381ecdac6213c6a132011d6","datavalue":{"value":{"entity-type":"item","numeric-id":3734170,"id":"Q3734170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$52C62E2C-35DB-4C61-8B80-E562E03B8BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"330ab4f4f17c0ee4717e95439890535a1926baa1","datavalue":{"value":{"entity-type":"item","numeric-id":4286721,"id":"Q4286721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$F4E081C9-3645-422A-A661-FAED3493C08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"731e99376e8702c5d355c7d2ba0ddb139c20b787","datavalue":{"value":{"entity-type":"item","numeric-id":3899825,"id":"Q3899825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$20335EAE-F1CD-45C5-A3B2-C145DD417F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21ba2c69ea8777972727ec5a44700a8aa08ceecf","datavalue":{"value":{"entity-type":"item","numeric-id":3026765,"id":"Q3026765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$F56BE5BB-55E8-4281-A3BB-98EF67ADEA81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be7d68ca9bfa4278b04d501d0092fc10e437a7a1","datavalue":{"value":{"entity-type":"item","numeric-id":4053351,"id":"Q4053351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$6B22E519-F544-4EBD-8788-39E7D250B75B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01ad617b9fb93b80038f5649c67e21ddf619ea3f","datavalue":{"value":{"entity-type":"item","numeric-id":3885546,"id":"Q3885546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$B00D201D-5432-4D01-A82B-EA95BF0A5F09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08681459d59a4941619e8e81c7e6055c81f4896d","datavalue":{"value":{"entity-type":"item","numeric-id":3778558,"id":"Q3778558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$81B93D3B-00D4-471C-8968-441D08280FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12c3b67e7f55bd26a414009861b48c39d2229cca","datavalue":{"value":{"entity-type":"item","numeric-id":4175066,"id":"Q4175066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$8895DAD6-04D2-47EB-B113-5DB8E2511FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$F8D45AA8-D515-4117-A2D7-8DE3C748AF81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a94965f92a0ffa4aeb120e0c98877d2cbff18f6","datavalue":{"value":{"entity-type":"item","numeric-id":3738933,"id":"Q3738933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$EE87B61C-6269-4015-9671-6EE2B3DA085A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d9278c22c170fbf7ab2ef157aff9ab68ae2346b","datavalue":{"value":{"entity-type":"item","numeric-id":1099780,"id":"Q1099780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$4C679D47-CFE7-4C43-AB7C-648C3494DA49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"895795a3d67334ec94a32b3f1ec5946ac8dc8cce","datavalue":{"value":{"entity-type":"item","numeric-id":1102861,"id":"Q1102861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$75B311C7-ADE4-414A-81CB-CC8C6769064B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6329aa3f53b0007d7c30145137b42eaa70d002d9","datavalue":{"value":{"entity-type":"item","numeric-id":5588250,"id":"Q5588250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$BB9C060C-91E6-4A97-A5F7-FFE3D6DE72F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ad59cfcb90b8ed4a5609c8ca2c7c1291344b0c5","datavalue":{"value":{"entity-type":"item","numeric-id":1821695,"id":"Q1821695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2276878$393BE343-0042-4D6E-BE0C-19CAFDAA4C0F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"349e13927ac9bbf873582d5bfccf841d238408dd","datavalue":{"value":"https://doi.org/10.1007/bf01588800","type":"string"},"datatype":"url"},"type":"statement","id":"Q2276878$E9957011-4318-4265-853F-B49F87D505C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"74861b3ce41d291bf8b9ae5d6f4cd351c9245eec","datavalue":{"value":"W2004732730","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2276878$458767EC-5712-45FD-86DA-9AD4B12C19F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"636f9ceb3acb0ae2a5c4d56e1f81a70370565a1e","datavalue":{"value":{"entity-type":"item","numeric-id":1905070,"id":"Q1905070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29ba710a07b6862eb874fdd4b8464b9ad93849a1","datavalue":{"value":{"amount":"+0.8188448548316956","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":"Q2276878$0CB235BB-A4B9-4514-BE7B-69BD904314D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a3cb2c5cc48d84eff3b79b9a1bf05fcabe29272","datavalue":{"value":{"entity-type":"item","numeric-id":1081534,"id":"Q1081534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffd4b19936492c95ad2911fa9f7c2c925f4e605a","datavalue":{"value":{"amount":"+0.8141081929206848","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":"Q2276878$33FF8CB6-1506-49D3-A30B-DD7234749525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"101acb63836e76dd367e406f6889bf82e5164435","datavalue":{"value":{"entity-type":"item","numeric-id":3475124,"id":"Q3475124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83240677890604c3ff96d57baff4cd8454ec5352","datavalue":{"value":{"amount":"+0.8133391737937927","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":"Q2276878$4F436D6B-0BB6-4CD5-9E66-5B80E38D8D7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b38f6cdd28924998b6decf4f7604274c6cf014bd","datavalue":{"value":{"entity-type":"item","numeric-id":3028724,"id":"Q3028724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43e8d6892da53edc0c87c9059338d1032cda65be","datavalue":{"value":{"amount":"+0.8057368993759155","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":"Q2276878$54668E31-CCE9-4015-A44A-4721D099205F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4525e7e161eaba2c367a7ee57817f635e66fa67","datavalue":{"value":{"entity-type":"item","numeric-id":3815132,"id":"Q3815132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47635cf98f1e051cc022915bcb7182a6997d7cc9","datavalue":{"value":{"amount":"+0.8007099032402039","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":"Q2276878$A782F174-474A-4A22-A62E-1D5FC29020E9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2276878","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2276878"}}}}}