{"entities":{"Q909581":{"pageid":911429,"ns":120,"title":"Item:Q909581","lastrevid":65276175,"modified":"2026-04-12T01:29:39Z","type":"item","id":"Q909581","labels":{"en":{"language":"en","value":"A probabilistic analysis of the multiknapsack value function"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4137530"}},"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":"Q909581$5B5B65F4-30C1-475A-86E2-9985EC2424A2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2847323a0d9448e9941d8f13056602dadc20ec8c","datavalue":{"value":{"text":"A probabilistic analysis of the multiknapsack value function","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q909581$603635E5-4C48-481C-B483-88450954559F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4ec70796313765704f2c838422d12aaaa3ecf4b5","datavalue":{"value":"0694.90072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909581$4223AB4D-21BA-4948-ADE3-7609ED8ED53F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ace0cb7ca8b4ff2b941946c4569530dd61c7e78a","datavalue":{"value":"10.1007/BF01585741","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909581$FD408D53-6723-4C70-BCC3-1E5C93FA3F5E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cea4fd5a14d528873471ba8a798664a58cdf3856","datavalue":{"value":{"entity-type":"item","numeric-id":909580,"id":"Q909580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909581$72C388AE-8004-45AD-B414-098BC79EB912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"35d6c381bbdf214787241481b862171fcb337669","datavalue":{"value":{"entity-type":"item","numeric-id":627159,"id":"Q627159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909581$CAD30A58-362A-4754-B1AB-41D372E8E93A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bd39037057f92722ad655aadbeb0b016d9c1d59","datavalue":{"value":{"entity-type":"item","numeric-id":797496,"id":"Q797496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909581$0931362E-0499-4223-B562-AE0ECD5E75C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15553ac1624d90cf309324297b60650885a8479b","datavalue":{"value":{"entity-type":"item","numeric-id":689139,"id":"Q689139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909581$23A49127-9DF3-4358-8C1E-B8A7F2D57829","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":"Q909581$1F42C746-4BA7-4125-B900-C5EF572823E9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q909581$F66F5730-E2E5-4879-B6D3-AD13B78C53AA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fdbac48a62c79b97d276cc55c71024466fd72a65","datavalue":{"value":"The multiknapsack problem is discussed. The problem is to minimize \\(\\sum^{n}_{j=1}c_ jx_ j\\) under the conditions \\(\\sum^{n}_{j=1}a_{ij}x_ j\\leq b_ i\\) \\((i=1,2,...,m)\\), \\(x_ j\\in \\{0,1\\}\\) \\((j=1,...,n)\\); where the coefficients \\(a_{ij}\\), \\(b_ i\\), \\(c_ j\\) are real nonnegative numbers. The problem is known to be strong NP-hard.    The behavior of the solution value of the multiknapsack problem with respect to changing coefficients \\(b_ i\\) is investigated. The coefficients \\(c_ 1,c_ 2,..\\). and the vectors \\(a_ j=(a_{1j},a_{2j},...,a_{mj})\\), \\(j=1,2,..\\). are assumed to be nonnegative independent identically distributed random variables and vectors, correspondingly. It is assumed also that the coefficients \\(b_ i\\) grow proportionality with the number n: \\(b_ i=n\\beta_ i\\), \\(i=1,2,...,m\\), for \\(\\beta\\in \\{\\beta |\\) \\(0<\\beta <Ea_ 1\\}\\), where the random vector \\(Ea_ 1\\) is the finite expectation of vector \\(a_ 1\\). Under these assumptions it is shown that the sequence of optimal solution values (properly normalized) converges with probability 1 to some function of the coefficients \\(b_ i\\), \\(i=1,2,...,m\\), as n goes to infinity and m remains fixed. This function is computed in closed form for special cases of the problem when \\(m=1\\) and \\(m=2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q909581$B4918CD4-8921-4074-84C0-624F449C657C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909581$63F91184-9D29-47DB-B82F-0D5C1DF1D560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909581$B7223944-3691-43B5-A2F5-AC6C5C86CC56","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0f71743f0e87322d54923b6d4727a6f3f457c037","datavalue":{"value":"4137530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909581$923C8234-BF1C-400B-A60E-CF21A0E8E756","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q909581$56416392-A592-433B-A1A1-205234323EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b99d11d534382549fef1e39a72dba526434b1f79","datavalue":{"value":"multiknapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q909581$206AC00F-B682-41F3-BA1F-76C35978AD60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72825277a59fba3c02518bf39e7d98cd9188f9cb","datavalue":{"value":"strong NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q909581$21D8EF01-57DA-4CA1-8F06-E247D7BD7661","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c54e16c51cf038e39d211f26a20642444a0ea747","datavalue":{"value":{"entity-type":"item","numeric-id":612204,"id":"Q612204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909581$51E71606-F996-4623-922B-32A24A8A3DA4","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":"Q909581$0669063F-A3E8-4359-AB53-23B877AAF734","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"68837032eafe701087759c4592975c0cf5d18d65","datavalue":{"value":{"entity-type":"item","numeric-id":3962773,"id":"Q3962773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909581$5467EF82-4C70-4953-88D6-82E123CBA947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"782678e2851b073dbc4e1a3115b6404d5118d182","datavalue":{"value":{"entity-type":"item","numeric-id":5588268,"id":"Q5588268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909581$47DBEC2E-E092-4DA5-997E-18FEAF0E4C12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d873eb220f9c7b9bab911767ca34bf21b911b7c8","datavalue":{"value":{"entity-type":"item","numeric-id":789319,"id":"Q789319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909581$F996B73F-163E-4153-ACF5-409927EC831E","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":"Q909581$27CA5C35-55FA-4A62-BD20-943F8F1243E9","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":"Q909581$C44C97FE-A688-4F6A-8356-E3A540BD4451","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":"Q909581$4EAE98EA-30F1-4A88-A74C-8E7166227B6B","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":"Q909581$615866E7-D90B-4865-A6A9-3B3C5B2EB74D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b20ca0fe9766fd759d373813c39f91a49f12ba6","datavalue":{"value":"https://doi.org/10.1007/bf01585741","type":"string"},"datatype":"url"},"type":"statement","id":"Q909581$C10B8E5E-4838-466F-801B-C37890B9FB5D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3fee47333b349298596298d377d78be8339b3393","datavalue":{"value":"W4246969534","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909581$9F675ECE-6C61-4F02-9531-87BD03322119","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fa8ca9ffccbbd5b16ff79c8cd0cbc8910c538fb","datavalue":{"value":{"entity-type":"item","numeric-id":3832316,"id":"Q3832316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e655bbc24f660ed4031461c9d6635b7d424a2fbe","datavalue":{"value":{"amount":"+0.8886352777481079","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":"Q909581$B667069C-F54C-46F5-974D-95B61D30F4E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2772cd27f11688c0a11f2d2cd2196e7402c9848c","datavalue":{"value":{"entity-type":"item","numeric-id":1181902,"id":"Q1181902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe3faca8d4ce308475d304f0ce95829ba1d83254","datavalue":{"value":{"amount":"+0.842032253742218","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":"Q909581$6C1610FB-A97D-450F-BC5C-33C53CC93AAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e9a91bd85d06bde46f3e63bb31fad59453fa383","datavalue":{"value":{"entity-type":"item","numeric-id":1371952,"id":"Q1371952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27749464756ee935cbe351402fc945d566c55b81","datavalue":{"value":{"amount":"+0.8404703140258789","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":"Q909581$D71B2B3C-FCC5-4945-9615-187098F1F881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e02f5034aeafcf2dbdb066c621e188e19a2aedf9","datavalue":{"value":{"entity-type":"item","numeric-id":789319,"id":"Q789319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e056d1a491912fe57b821a6977dfd5fccc6b885b","datavalue":{"value":{"amount":"+0.8393157124519348","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":"Q909581$C3C0080B-BB72-49F2-8B51-D25F5277B642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f609d110cf2f032580fc7da79050dc92ebd505e","datavalue":{"value":{"entity-type":"item","numeric-id":3494383,"id":"Q3494383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39565405b38a3e4f601d2e1bf070563973e11430","datavalue":{"value":{"amount":"+0.8349622488021851","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":"Q909581$AA614212-9182-48AF-AFAA-920F3AB501AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A probabilistic analysis of the multiknapsack value function","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_probabilistic_analysis_of_the_multiknapsack_value_function"}}}}}