{"entities":{"Q1974584":{"pageid":1985326,"ns":120,"title":"Item:Q1974584","lastrevid":43458848,"modified":"2025-07-26T01:28:59Z","type":"item","id":"Q1974584","labels":{"en":{"language":"en","value":"A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1439909"}},"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":"Q1974584$D09B0A54-8312-440C-8A37-8CE50F04C93F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5559f6e9d92f19428b90a394043168ce6a0cedc9","datavalue":{"value":{"text":"A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1974584$E04E9F7E-0169-47AD-BA22-3896F6E7025E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c77bcc9d863485d97c7efdad21401b5aa623d698","datavalue":{"value":"0949.90059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974584$5BD02730-9FFB-4A3B-B212-5AE7267E3057","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c24052ca3a8af9cb81b063b423487047d424c77c","datavalue":{"value":{"entity-type":"item","numeric-id":486943,"id":"Q486943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974584$FE76F1A4-B7EE-44B2-86F6-99A21DFEFC08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a2454aabe2ca9776b7c237f81e431fb096033f2f","datavalue":{"value":{"entity-type":"item","numeric-id":1002050,"id":"Q1002050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974584$55EC3665-DF13-4F7D-8C7F-E363FE2A066F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a1409dc6862a31a77f154ad0a1f54092232038ca","datavalue":{"value":{"entity-type":"item","numeric-id":244038,"id":"Q244038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974584$F57E1E1A-E3C0-4038-9141-0AD6C6875B77","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cc17136081e6b5d5fc40d3affb0beecbc4f23a8c","datavalue":{"value":{"time":"+2000-05-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1974584$ED36983F-1059-4DE0-B37E-BCC419E1D3DE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cafaff8599aebb411a381786f51798ecdb02241f","datavalue":{"value":"The paper gives a lower bound on the average number of steps the simplex method needs to solve an LP problem. The important feature of the result is that it is valid for all variants of the simplex method. Variants differ from each other in the rule how they determine the `next vertex'. The problem under investigation is: \\(\\max v^T x\\) subject to \\(a_1^T x \\leq 1, \\dots, a_m^T \\leq 1\\), where all vectors are in \\(\\mathbb{R}^n\\) and \\(m\\geq n\\). Additionally, the problems are randomly generated according to the rotation symmetry model, i.e., \\(a_1,\\dots, a_m\\) and \\(v\\) are independently, identically and symmetrically distributed under rotations on \\(\\mathbb{R}^n \\setminus \\{0\\}\\). For the expected number of steps of the simplex method the following lower bound is attained: \\(E_{m,n} [s^{var}] \\geq C m^{1/(n-1)} n^0\\) for all pairs \\(m\\geq n\\) and for all variants, where \\(C\\) is a constant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974584$13C81A40-938B-44A2-8369-EFC98372F01D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c5bd3c1f398eb3bf06a0af243f0673a8a59d7bf9","datavalue":{"value":{"entity-type":"item","numeric-id":240126,"id":"Q240126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974584$760E6CE0-4E9F-43CD-87D2-BAE818BCD763","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974584$35CEA4A6-6AB7-4404-8164-9B3D4361239D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974584$B371E2FB-DC72-4612-8108-FD4008942635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974584$2A488676-6448-4BDB-B911-F15555065B3D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ff28e52f01480fd71992fad2b593900d3064296","datavalue":{"value":"1439909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974584$87C41A71-E2F1-484C-A34A-080015200410","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974584$0E38FA00-66A7-4CFD-9D45-1A95BA5219B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeb5cf5222b6371fb7f9c168c78eb205663c9be7","datavalue":{"value":"average-case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974584$0BEDFAEF-A330-4534-AE63-A13E504E14F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974584$839E05A5-261B-4F1C-A815-D986E09062A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6a9e644a062c5b7767e4219356e03dc48d7fb21","datavalue":{"value":"simplex method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974584$45518114-A363-4DB0-9C1F-E717BDBDDD47","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":"Q1974584$B7F5C410-0BF6-435D-B59A-817D4DCBD7F9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6db115499696719dbab01351acbff2f77c15f2d","datavalue":{"value":"https://doi.org/10.1007/s186-1999-8373-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1974584$4091186E-7758-458E-859A-905052DB4965","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c03403b26cfdad9f85b4057148093dcdeccb1ba6","datavalue":{"value":"W385102008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974584$3534818A-9B6A-455E-AEA8-61DE55245946","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26e7a92bf4da6353bc88b90af47e29a2e53f12d8","datavalue":{"value":"10.1007/S186-1999-8373-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974584$1051243C-01E3-495D-A2E4-6141E2E1D2C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07609a913d6b318d4f50f2b23bc5f6a3793b1410","datavalue":{"value":{"entity-type":"item","numeric-id":1100853,"id":"Q1100853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acd62c7923da748aa204cd0dc2a803355e1e8089","datavalue":{"value":{"amount":"+0.9193113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1974584$B11B95FA-96D7-49B8-A507-5C8EF57518A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3cee5830ffccc365c61d7a37d5fcbaa5d7e8579","datavalue":{"value":{"entity-type":"item","numeric-id":3755232,"id":"Q3755232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e935ffda3e65e16ce44c08ce0b096a2cb95acad","datavalue":{"value":{"amount":"+0.9064418","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1974584$CAA65DF9-D906-4E61-B482-3A169E30EF71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dffa3c8989f6fffa366adfe0815507a306b477e4","datavalue":{"value":{"entity-type":"item","numeric-id":4845092,"id":"Q4845092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39cc4282cb1e625294f135b6f2f2291f3b806941","datavalue":{"value":{"amount":"+0.905738","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1974584$020EC7D4-9D80-4D5E-8305-58336FE13AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcf7cd0eca1ea92abee9c0c96bf04b01bdd5bd3e","datavalue":{"value":{"entity-type":"item","numeric-id":4716334,"id":"Q4716334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"346824b58326f1258e9a6e20a0c1b4212620aa1c","datavalue":{"value":{"amount":"+0.89464694","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1974584$72996941-D1E0-489C-A792-5ADC6933E867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc8d7e49bdabd530c0424a7cebe8bbc62acb8649","datavalue":{"value":{"entity-type":"item","numeric-id":1068713,"id":"Q1068713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c21883eed9e21629725328e76d98c19d53f0475","datavalue":{"value":{"amount":"+0.8817141","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1974584$77AD52D0-C536-4B00-A068-E0E4A1CBF6F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de03e4f4d407054edb0725e29094bf57969246fe","datavalue":{"value":{"entity-type":"item","numeric-id":5419098,"id":"Q5419098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9078ac7904f8c5e15e523d5a52ce2c88d30eea54","datavalue":{"value":{"amount":"+0.87182295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1974584$B275841F-4E01-4941-9DB0-A39E3DFA5680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2f81a65b38cb07b42c08648c6b69704429fbcf7","datavalue":{"value":{"entity-type":"item","numeric-id":1915913,"id":"Q1915913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37d39697e998ee4e75fad25aa7be03a98128ea57","datavalue":{"value":{"amount":"+0.86965257","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1974584$ABEE2F0B-1BF5-41E1-ADD8-2E8D1169DB4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da6c67cb8f79a91b4bc730526875f38dfc94825a","datavalue":{"value":{"entity-type":"item","numeric-id":4288560,"id":"Q4288560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a169342522aa5f563c83ce0380ce233f1915bea2","datavalue":{"value":{"amount":"+0.86845934","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1974584$3FFAAC30-68FE-4FB6-BC7A-D211257A9E02","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1974584","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1974584"}}}}}