{"entities":{"Q1338142":{"pageid":1348881,"ns":120,"title":"Item:Q1338142","lastrevid":67478523,"modified":"2026-04-12T18:16:30Z","type":"item","id":"Q1338142","labels":{"en":{"language":"en","value":"Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 695783"}},"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":"Q1338142$11C80618-7E71-4AB4-A554-B05A58A22CD8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"90e5ff86e1029d4e738eb4dcae2e2df3e0140830","datavalue":{"value":{"text":"Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1338142$454AF4A3-27FB-44D7-A4D8-1A09C9CC0284","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"854dffde74c8f77d3401abbea28b35a1e4605acc","datavalue":{"value":"0828.90090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338142$3093B7B3-2053-4AE4-85A5-4DDDD8125494","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"63fec65bfeb56c5a57a1a6338d1c40f6497dfb1c","datavalue":{"value":"10.1007/BF01581700","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338142$649AE156-DAEB-47BC-875D-1FBB38DB309E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"856cdffeb9dc8763a415f7f3007c75a417723627","datavalue":{"value":{"entity-type":"item","numeric-id":185363,"id":"Q185363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$BB00B021-3356-473F-AAC6-5B992CA100F8","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":"Q1338142$DF71C237-A791-443F-BD9F-DAD5790D8359","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e26d9462e0cc2514efa9fd1ce559f205339e5ef5","datavalue":{"value":{"time":"+1994-11-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1338142$0B5274AF-8007-4E6F-AF14-E71C73D82156","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6dded11eac64d4fe385e0b26a21f38b5361a61ee","datavalue":{"value":"Characteristics influencing the efficiency of Lagrangean relaxation algorithms, such as the probability of the existence of \\(\\varepsilon\\)- optimal and optimal \\(\\delta\\)-feasible generalized saddle points of the Lagrange function, the magnitude of the duality gap, are investigated. The probabilistic analysis is conducted under the assumption that the coefficients of the multidimensional knapsack problem are independently distributed. In section 3 the author derives several general sufficient conditions of ``good'' asymptotic behaviour of the mentioned characteristics. In section 4 several specific classes of probabilistic models are introduced in detail. For each of these models explicit formulas for the optimal Lagrange multipliers are derived and sufficient conditions are expressed through the parameters of the model. In the last section a fast statistically efficient algorithm with linear running time for the approximate solution of the problem with random coefficients is presented. The paper is clearly and precisely written and can be highly recommended.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338142$777CB670-858A-4868-9B6C-9630289F1BCC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338142$02605E02-0D0A-4722-A9DA-8B8687FEF8B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338142$A152A1E6-EE01-4ADF-9F31-172522DD702C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"81555ee6d3bdf961cf9ad230ed781136e8075e24","datavalue":{"value":"695783","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338142$9F2E4C79-C1D2-4D77-85DF-6595CA129370","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5dffc200702e75861cfb412bbdf1a893cc6941d7","datavalue":{"value":"efficiency of Lagrangean relaxation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338142$CC8C575F-AC4F-4F7C-93BC-30BEC81556C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338142$5DD1D989-DE7B-4AA4-9EFD-E6435C7C2A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd9f81e2de676ca1bc7efadeabffd39fb5463e86","datavalue":{"value":"knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338142$37E50834-BCF7-4830-9DCB-079A1B31C119","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":"Q1338142$79F2C360-ED49-4E02-B89F-C5DE3EE62DBC","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":"Q1338142$3E8AC532-0253-4C48-9807-A704995EC67E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"22efb9ef6454847970e9f94c68cf86deea1d38a3","datavalue":{"value":{"entity-type":"item","numeric-id":1168896,"id":"Q1168896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$BCDFA5CD-4C9A-4C36-96B8-B3F1277B5C23","rank":"normal"},{"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":"Q1338142$3C6AAC23-7597-4647-8685-1E56CB6041A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ee5daeabab453dd5220193600eedacb2f30d574","datavalue":{"value":{"entity-type":"item","numeric-id":3494383,"id":"Q3494383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$5731247C-D702-4F19-9F19-09F9E29A3177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52661e4c25b26957af4b6280040e7df9eb671605","datavalue":{"value":{"entity-type":"item","numeric-id":3487140,"id":"Q3487140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$572E627F-333D-409E-B0D3-46429417C42E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e3e2312b1eb568d0fcbb0a84ca405d008834f6a","datavalue":{"value":{"entity-type":"item","numeric-id":1824560,"id":"Q1824560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$C80F8B1A-5D28-4B03-B658-BCD1D90EAEE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"613599edc92e38a46f3320b4b5514096fcd17234","datavalue":{"value":{"entity-type":"item","numeric-id":3850361,"id":"Q3850361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$5CC6D03D-DE9B-4B83-A061-1B2B84E39BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"083d97e730faf90a4132402a3f045bdbf076bc3c","datavalue":{"value":{"entity-type":"item","numeric-id":3919449,"id":"Q3919449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$BC09A206-4ECD-4DCB-8BE4-A4BBCFA58746","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":"Q1338142$F7975E49-AAA4-4A70-BE0A-88848C199776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"868166a76add5f645d9642728fb6613e5dec0780","datavalue":{"value":{"entity-type":"item","numeric-id":1077329,"id":"Q1077329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$039D41BD-4147-4CCE-8ED1-AA2F1DA77268","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":"Q1338142$50615718-BE14-4A5E-890F-FB669051CAF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3e32cd00e50889ce6fdac19be614a9be1a54020","datavalue":{"value":{"entity-type":"item","numeric-id":4164569,"id":"Q4164569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$CE5ED03E-8EF5-46E1-86DA-5C3394DB61B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ca26a6356e7bc5cb8544ed72c382accc16a1280","datavalue":{"value":{"entity-type":"item","numeric-id":3824101,"id":"Q3824101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$E4F0D62A-26F1-422C-93FD-B26898780006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95c101f437443df62986ba3448bd1d0cc4205b19","datavalue":{"value":{"entity-type":"item","numeric-id":4198339,"id":"Q4198339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$0D544A62-79FC-4974-9BDE-380B6911C407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e199df9795f6d672ad0bc83a43a3dc86147c6662","datavalue":{"value":{"entity-type":"item","numeric-id":1162147,"id":"Q1162147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$66B729B9-ED6C-432B-BF61-404CCFDC3F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38d81f870e884722cebc6e9b1d03797007b43414","datavalue":{"value":{"entity-type":"item","numeric-id":3343773,"id":"Q3343773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338142$B7279394-1FE4-4974-A1C3-24F7620DF4DA","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":"Q1338142$E5F8EDCF-5949-4DEA-A52B-BB1B111898B3","rank":"normal"}],"P1643":[{"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":"292f231d93424e673c6ece7e7c133824c0d81a3f","datavalue":{"value":{"amount":"+0.8665179014205933","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":"Q1338142$361F1597-BB65-4B9C-AE64-936B3B6D6AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fd9b5bea190fb05113f4342197ce56a67e050f7","datavalue":{"value":{"entity-type":"item","numeric-id":3211110,"id":"Q3211110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d1ded061435181b503373bac4279ab0c4ffa58f","datavalue":{"value":{"amount":"+0.8429051041603088","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":"Q1338142$5BA79F11-5D71-4B8F-9604-A42E037EA1D9","rank":"normal"},{"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":"e1ceb0654d87baef301252157e65b8613288090f","datavalue":{"value":{"amount":"+0.8279630541801453","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":"Q1338142$74A235F4-8631-4158-B773-4325D7E5506D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0413cd011bbd6374a3e6f56ba75508a0d03ec21a","datavalue":{"value":{"entity-type":"item","numeric-id":3487140,"id":"Q3487140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8725b42800718d13a31bb9683639897c29363cb","datavalue":{"value":{"amount":"+0.8054024577140808","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":"Q1338142$35572FC2-CA08-4595-AEDF-068572FE319D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd0b03df2013ebf3594c0a03182316da2c7d7219","datavalue":{"value":{"entity-type":"item","numeric-id":909581,"id":"Q909581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ba3c6289aa75018e7a19acae758b0452375a038","datavalue":{"value":{"amount":"+0.804008960723877","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":"Q1338142$01237F50-6A57-4BDB-970D-38657AB769CF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Probabilistic_properties_of_the_dual_structure_of_the_multidimensional_knapsack_problem_and_fast_statistically_efficient_algorithms"}}}}}