{"entities":{"Q1112724":{"pageid":1123473,"ns":120,"title":"Item:Q1112724","lastrevid":49229452,"modified":"2026-01-06T19:39:21Z","type":"item","id":"Q1112724","labels":{"en":{"language":"en","value":"Probabilistic construction of deterministic algorithms: approximating packing integer programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4079166"}},"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":"Q1112724$A669E142-5B56-4E74-B4AF-72B2EA87CC49","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"96fe5a82a044a8d330352f27f1794a3c888596ad","datavalue":{"value":{"text":"Probabilistic construction of deterministic algorithms: approximating packing integer programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1112724$6F977FCD-BFA3-4B11-9434-E5FE9FAC717F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"62f1cc59cf3706d99d0411615371d8a52484574a","datavalue":{"value":"0659.90066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$A01EF51C-5A2E-43C7-A2C2-3B10CF405B7B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6268950b47f2eac8d490de3d48891cd28c80554","datavalue":{"value":"10.1016/0022-0000(88)90003-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$EEAF474E-2C46-4B0A-995B-EBFDF0C902CB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$3AA5E338-AE24-4C28-BC89-EDC96DFC40EA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1112724$913BE61B-A9A4-490C-A56A-99470E846F10","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"57a29e8a8372eaa1c536184b6aa0fc2d83728d2a","datavalue":{"value":"A matrix \\(C_{n\\times r}\\), \\(c_{ij}\\in [0,1]\\) and a vector \\(p=(p_ 1,...,p_ r)\\) are given. An integer vector \\(q=(q_ 1,...,q_ r)\\) that approximates \\(p\\) is computed. Every coordinate of the vector \\(\\Delta =C(p- q)\\) has to be ``small'' in absolute value. By methods taken from probability theory the author proves the theorem: there exists a vector q such that \\(\\Delta_ i\\leq s_ i\\) \\(D(s_ i,1/2n)\\) for \\(s_ i=(c_ i,p)\\), where  \\[ D(m,x)\\leq (e-1)(\\frac{\\ln 1/x}{m})^{1/2},\\quad if\\quad m>\\ln \\quad 1/x, \\]  and  \\[  D(m,x)\\leq \\frac{e \\ln 1/x}{m \\ln ((e \\ln 1/x)/m)}, \\]  otherwise. A deterministic polynomial algorithm is proposed for finding such a vector \\(q\\). It traces a search tree from a root to some leaf without backtracking. At the next node a component \\(q_ i\\) is determined by the use of estimates for \\(q_ i=0\\) and \\(q_ i=1\\). The procedure, called ``method of conditional probabilities'', is applied to vector selection problems, packing problems and maximum multicommodity flow.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112724$9C58FDFF-5256-45E4-9326-5C2ED58FB27B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$2F97D5FE-475C-4DE8-AE09-28AC71FC7C71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$A1671F1C-31B6-4B2A-8E84-DB03F4DEC7BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$F0AB4778-F76E-457F-A377-7C0C7F5CBA4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$38774483-B9C6-4159-96C9-0B79353449D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$C3754E1D-7CF9-42A4-B2CA-7FDBB07A9304","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2a3542468856bcf6fc71a1f5c51a9f5f5f6fa658","datavalue":{"value":"4079166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$D6226B96-2C81-4D8F-B061-C76CB4AECD26","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88d4d94e4f7cb04320063f664166fa5ca067fe66","datavalue":{"value":"randomized rounding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112724$AE919E4B-0751-4DE2-91F3-27F1973627F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112724$65065585-BE7E-4C59-A6EE-93E837EEA82A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3eb0e3f35aee16e3e6ef85bdb9740a7cee2d7b7","datavalue":{"value":"method of conditional probabilities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112724$F5C08238-D701-4056-81A0-B6170F05791D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8227c5e3f7245ec24de58b227c4e5cb94442fcdc","datavalue":{"value":"vector selection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112724$CDD68BDE-C2F7-44C5-B67B-1347A8856B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"093ef3cbea03ec661dc66ae3009ad13581b7249b","datavalue":{"value":"packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112724$6B85AC10-FAEB-4414-B945-E7C90536F4FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1726defc73fd53c522aa12d4ab22ccb43e42a1","datavalue":{"value":"maximum multicommodity flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112724$360A7EA9-E17E-4C91-9D23-B8C45548BC11","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b0fb0f2c86e93cd39417ea5519157255e289364","datavalue":{"value":{"entity-type":"item","numeric-id":222782,"id":"Q222782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$751A3E19-7950-49C3-A07E-9A3A63A45B56","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":"Q1112724$1A19E45D-530B-4BE3-A98C-037DF5FD655E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"90f28fa0f632fc70a05f9410d409862ff9fe42bc","datavalue":{"value":"https://doi.org/10.1016/0022-0000(88)90003-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1112724$F88E4948-22B7-413F-A42A-3DEBE6E127F2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9960bce00c6247b350f465c85e3d5d4d9613891d","datavalue":{"value":"W3011766368","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112724$702AFC5A-A23A-49B2-A4B7-6C2C205DBC0E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$72C31A8D-2F02-49A6-92EA-F1F97A902E75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bd7a8ce486ca7ade9cf050702e6d5793fe88a9f","datavalue":{"value":{"entity-type":"item","numeric-id":1158443,"id":"Q1158443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$58FFB8B5-860A-4787-A601-A1F27D6A6A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$1328E0FC-8F70-4411-8231-11E570F0BBC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$8063A76D-AAC0-490F-A2C8-3E792B53F46B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$9983FC8C-75D9-4E7A-AF9A-F428D88ECC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f744b48e1b7262e1ddf22a98deec4513fab3e800","datavalue":{"value":{"entity-type":"item","numeric-id":3710289,"id":"Q3710289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$DB2FD9B4-4813-4A56-B324-75A13804A156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$97CA906D-B799-4F5A-A7E2-29F5C0ADCD27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$42D859E6-2EEE-4234-9750-F6547DF74CD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8104acbfbcda2b7a64c84031b5436962bb027ece","datavalue":{"value":{"entity-type":"item","numeric-id":1097238,"id":"Q1097238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$9A83193D-35DF-40E1-BAB8-4FBE92CB6C3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$C16645B3-643D-469C-9F8C-0612A4385877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f590d56cd7ed23c2f82466b0e2b12190ee8869d","datavalue":{"value":{"entity-type":"item","numeric-id":1250818,"id":"Q1250818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$73C4CA0F-F53B-4479-A234-D9F7226C09A5","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":"Q1112724$8E07DEA6-5189-4A49-BF36-286A8A20D141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0611c8fede42ac100885c81ef1a90e51ba7e3b3","datavalue":{"value":{"entity-type":"item","numeric-id":1106724,"id":"Q1106724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$6EAADBC7-1EEA-41CC-8B07-F246226CA48A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21ca101024d871b1209ca96a11a1f5f21eda2ef7","datavalue":{"value":{"entity-type":"item","numeric-id":3698810,"id":"Q3698810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112724$0C2008A7-F970-40E7-9F76-A86DE9FBBDE9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb36ffee1426747e74025dc4108c7ba175c95c9e","datavalue":{"value":{"entity-type":"item","numeric-id":3569012,"id":"Q3569012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"779a06d6a8592b2f17f06ec440b6d395dfcf80db","datavalue":{"value":{"amount":"+0.809119701385498","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":"Q1112724$2B3038FA-F82C-4969-879B-9C539A20348C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef3ac78865e81d1c2ebcafbb54195eb767ea48d1","datavalue":{"value":{"entity-type":"item","numeric-id":4234073,"id":"Q4234073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f137481528d4cf536144e7ad7dffe44997cfeda","datavalue":{"value":{"amount":"+0.795791506767273","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":"Q1112724$CA91CDD8-9CF4-4879-A328-555DA0148244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"104dfc39e9ec41ce357ce7cab99436afd7755762","datavalue":{"value":{"entity-type":"item","numeric-id":4522859,"id":"Q4522859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1bd4cd3b9d66021a47530ca26770ecb6daa01a3","datavalue":{"value":{"amount":"+0.7944627404212952","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":"Q1112724$EAF394C6-1862-4A96-94F7-275C4203D77E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1303dfda835a3c5af6d41fef389ee38c2cdb03b2","datavalue":{"value":{"entity-type":"item","numeric-id":4395335,"id":"Q4395335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23977704f56e4324e47ce031fd15f001374e8fcd","datavalue":{"value":{"amount":"+0.7862459421157837","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":"Q1112724$3D0ED3F8-5F40-4D3F-8CF0-D1CFF8BA0B6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9584e42778cb3cddce78a7d467e8e04f78fad4c","datavalue":{"value":{"entity-type":"item","numeric-id":4868265,"id":"Q4868265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1124872ce9545864c7bb522dc96bdc3cf066a73","datavalue":{"value":{"amount":"+0.7856525778770447","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":"Q1112724$A0379CDD-B9FC-4F4C-AC66-AD47945F5236","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1112724","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1112724"}}}}}