{"entities":{"Q2483208":{"pageid":2493951,"ns":120,"title":"Item:Q2483208","lastrevid":50344907,"modified":"2026-01-13T20:57:47Z","type":"item","id":"Q2483208","labels":{"en":{"language":"en","value":"On the probabilistic complexity of finding an approximate solution for linear programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5268303"}},"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":"Q2483208$FA825F53-2A0E-4B9E-A85A-12F4570610A2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8b6d90429d9ef21876a93562acd7627fedcef198","datavalue":{"value":{"text":"On the probabilistic complexity of finding an approximate solution for linear programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2483208$B22BE4AA-9350-41AA-BABE-034154B5C851","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"33016d8a2412b40af83cd3a84bb556e04f04fc5f","datavalue":{"value":"1141.65043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$21A46220-929A-4557-8038-A094CB786101","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"82c3b50654a9f27d47289e3cb873a68ae4ca5fee","datavalue":{"value":{"entity-type":"item","numeric-id":278620,"id":"Q278620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$183C1FD2-3E12-4759-B516-E9911A99D2F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"796ff6540b98b3a4a57c2cf4aa26df17c883effe","datavalue":{"value":{"entity-type":"item","numeric-id":229630,"id":"Q229630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$FFEDAD18-20C2-4561-9690-A9D64D625BC0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$92641AD5-9E4D-455D-A7F5-AB784B92767F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5e04dc5261c233b410a9337ed726ed89fa4df984","datavalue":{"value":{"time":"+2008-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2483208$AC47BF8C-934C-4449-8D41-9555CBFECFCD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ae660705f6ac17f2f38c16b99646b55e823c540","datavalue":{"value":"The authors study the problem of finding an \\(\\varepsilon\\)-optimal solution to a real-life linear program. They begin with a useful overview of the literature on existing probabilistic and worst-case estimations of the complexity of solving linear programs and then continue by presenting their probabilistic model for which they then describe (with proof) asymptotic results, convergence properties and average number of iterations required to obtain a solution with a value within \\(\\varepsilon\\) of the optimal. Several useful theorems are proven in the course of this paper, which concludes with a list of very useful references.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2483208$58719BB0-B69A-45C1-8057-C51FAA5F577B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"58309c80337e7309a39fa8b39c69e1b722b3cd2b","datavalue":{"value":{"entity-type":"item","numeric-id":590170,"id":"Q590170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$FEF7E93F-8DD6-4159-AD6C-A586127CC943","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$96F7214E-4186-4A73-8B84-9C7C28FE35DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4ac3edbc9a781214f87fc7c9c04c2c17e13b7ca7","datavalue":{"value":"90C51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$E0FAF909-4946-4F98-AFF5-632323853AA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$BED15613-7887-447D-86BE-41ADEC9283F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$3BE3A2D7-DF33-4359-8785-BDE5B6B87E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e038e5e16128fe63d90643b4c4804d63f3db1339","datavalue":{"value":"90C06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$73F05027-9FDD-4B63-A5FC-620F97A67E08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$EA23A117-9B10-41BE-BDCC-A910BE76227A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$941F4696-7989-45AF-B12B-DC17DB7BA1EB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fe05eddc3d3b02681a49e11eabfa9080dd088fbc","datavalue":{"value":"5268303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$D6973389-1698-40E4-8B50-EDDFC842B4A1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2483208$57D51644-2A0A-437F-A0A3-D1D94151A0A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9b1150e0197512a81f8177f131bb1f888c369f5","datavalue":{"value":"interior point algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2483208$940A5337-E589-402D-A759-3712877E94D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f5be192625e7ec06f60848bf5fa4300b42d88bc","datavalue":{"value":"average complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2483208$BA536D50-31A3-4E69-B8F1-FEC44B332B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9d9df214c6fc201e3492fc82e0f92f4e25cd888","datavalue":{"value":"approximate solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q2483208$99FC20D3-BB77-41F1-AB24-CB2ADDB10A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d97a0d8b98e33725e65f45a7ce88d27fba0f45cb","datavalue":{"value":"worst-case estimations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2483208$4BB28C98-C24D-4FAC-B5A3-657358EBD22D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d96e0ed81d2469df094a87982571c9ec66d7dd18","datavalue":{"value":"probabilistic model","type":"string"},"datatype":"string"},"type":"statement","id":"Q2483208$803BC383-63ED-414A-B2FA-6C2148DBA31D","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":"Q2483208$FDBF1972-0718-4724-81D5-9946EB13610D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"99b10dab6bcd70e89b0b423db92397ca6588d02e","datavalue":{"value":"https://doi.org/10.1016/j.jco.2007.05.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q2483208$D53487E7-435A-4A6F-B799-D33892791FAF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d39c98123ee15e2fbd91b0fcb1d41d8ac19b4997","datavalue":{"value":"W2115947196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$636D97B1-7CC1-4804-833E-84A94EE699A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba58aedcf579fa5dbe76f99feadce616f0836fb2","datavalue":{"value":{"entity-type":"item","numeric-id":5202841,"id":"Q5202841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$50A5C7BD-75E8-4B22-84B9-5688EFDE6265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8c35433c1f9613e6e4bfce80f0acd95698d6ed6","datavalue":{"value":{"entity-type":"item","numeric-id":2743961,"id":"Q2743961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$C40DFCF8-9C46-4402-86E0-D4F6C4A93191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"268bf06e5ed34aea547df28a1452604cbf984ad1","datavalue":{"value":{"entity-type":"item","numeric-id":2757589,"id":"Q2757589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$75551E28-68C3-425D-A242-5A0EDE81224D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cdd0b70f35d727a15349c754206735e25795396","datavalue":{"value":{"entity-type":"item","numeric-id":1097170,"id":"Q1097170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$4B65B512-CC91-4E6A-ABB1-B231190A7D73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abefc9928deb9f7d79f04f6a66a33b8147fc8660","datavalue":{"value":{"entity-type":"item","numeric-id":2757618,"id":"Q2757618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$46E5EACE-19F6-4CA6-9FFF-5011DEE2E541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"717fead3bb2f018d1e5c9527fbd00dffded80f65","datavalue":{"value":{"entity-type":"item","numeric-id":4045381,"id":"Q4045381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$4D4F60A0-6083-47FC-A57A-A3F0AAD1D774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d2fe4872882185c04ce0e93466dcf969ef3bc8e","datavalue":{"value":{"entity-type":"item","numeric-id":689124,"id":"Q689124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$49A87DF0-CF49-4BA8-856C-A11985D20041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcc95ed8e6dab2eb2fa879f242f6a27674188e97","datavalue":{"value":{"entity-type":"item","numeric-id":5586854,"id":"Q5586854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$CA9D7F85-A34A-4049-A642-7DFE8526B33F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af4a4c7242adb6bdc7fe4972baf5730dad8dbf1b","datavalue":{"value":{"entity-type":"item","numeric-id":1589768,"id":"Q1589768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$65C240BD-5B3B-4945-89AE-DFD5FEB9C582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04fb91420057ec40a826a070c6e1f9ecc9a0e226","datavalue":{"value":{"entity-type":"item","numeric-id":1872636,"id":"Q1872636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$CF9E4733-C13B-49EA-A163-B5940225D3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7687a2c040ff3812a1fc2b7dd0610e635b260aa0","datavalue":{"value":{"entity-type":"item","numeric-id":4286944,"id":"Q4286944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$3DF217B2-9256-471A-B9F0-AD25963C59AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0387d62c6ee650f059930e6c57169d1a38adeac8","datavalue":{"value":{"entity-type":"item","numeric-id":3040925,"id":"Q3040925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$526CCF26-1AE9-4B36-811C-86994B97AA28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cdc44d9de3b3c9b8575826a5ed4045d047ba761","datavalue":{"value":{"entity-type":"item","numeric-id":3989814,"id":"Q3989814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$08884A8D-EA1E-4353-84E4-70511376E110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27281752750ef8f4d88eb11d5db3bc66924c022e","datavalue":{"value":{"entity-type":"item","numeric-id":5930724,"id":"Q5930724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$02FE1A0C-69B3-40B8-AFD9-C3C3FCCF9190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe09442c45daf3a6b51c358a7949ac67a755ae55","datavalue":{"value":{"entity-type":"item","numeric-id":3211107,"id":"Q3211107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$F2F90EF4-BFC4-43D9-823A-D1521DBE990A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3380ab9c3e3b64f9dfc0465d6b5a7d3e3ddf0a74","datavalue":{"value":{"entity-type":"item","numeric-id":1165154,"id":"Q1165154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$7057D219-1C9D-4A33-8B11-26F1BABC4C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee7b48ddb29fbf07e8e1049797547bb89f315cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1352307,"id":"Q1352307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$DB549E41-7519-47F0-B796-38BE65BED2B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cce6c1aafdda613b11f4f93faa6aafaf79132b4","datavalue":{"value":{"entity-type":"item","numeric-id":4294728,"id":"Q4294728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$66FFE033-AD27-4EE8-BE8F-AC647670245E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edfb1b7763a0c4062e90a20e69574676676fc93c","datavalue":{"value":{"entity-type":"item","numeric-id":2368076,"id":"Q2368076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2483208$48A867EF-2721-43AE-81DD-D05DD9670125","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8880540ebf1095204f48ada2e657e0f603bd828a","datavalue":{"value":"10.1016/J.JCO.2007.05.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2483208$BF1BE312-C156-49E7-A3E6-115E1DEC6CAA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7305cac42ad462ba24e0895038adee1b4120750e","datavalue":{"value":{"entity-type":"item","numeric-id":4294728,"id":"Q4294728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"565d60ec3c7dadb5adc88bdbb7d3c2f6d12c614b","datavalue":{"value":{"amount":"+0.8342315554618835","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":"Q2483208$5D0B0E43-2C6F-4808-B2C0-96B20AF50788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed5d95cbe5f6f4bba88b2803a5468f3e96e06863","datavalue":{"value":{"entity-type":"item","numeric-id":2757589,"id":"Q2757589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5473adb105bb1adb52bb6a6e8c17a7a851c8923","datavalue":{"value":{"amount":"+0.829073429107666","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":"Q2483208$AACF857B-65BB-4D0F-8D0A-381507814299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f08090daef64cf642558404b847671186c4c022","datavalue":{"value":{"entity-type":"item","numeric-id":1002052,"id":"Q1002052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cde6309afcb4ac4818d5c35a79020cc8ff32f22","datavalue":{"value":{"amount":"+0.7997531294822693","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":"Q2483208$93E6E04F-D260-40CF-B76D-B4644261C1BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6f2c6fbab9e656440347da86a290e6721664d95","datavalue":{"value":{"entity-type":"item","numeric-id":4664936,"id":"Q4664936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cefc89851111fef83ad10ccfce1fdafdfd9ebc62","datavalue":{"value":{"amount":"+0.7965176701545715","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":"Q2483208$F69EC5E0-5681-47DD-9D8C-12BE37F50AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4747780b0e9e9205aede104cdbda76bfec87a68c","datavalue":{"value":{"entity-type":"item","numeric-id":5202839,"id":"Q5202839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48fe41244df14dd6c532f644283cb42ff8f30bb4","datavalue":{"value":{"amount":"+0.7917790412902832","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":"Q2483208$97A64DE1-CE1C-4B9D-8198-B211FF188BFD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2483208","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2483208"}}}}}