{"entities":{"Q1100853":{"pageid":1111605,"ns":120,"title":"Item:Q1100853","lastrevid":69641160,"modified":"2026-04-13T08:23:55Z","type":"item","id":"Q1100853","labels":{"en":{"language":"en","value":"A simplex variant solving an m\\(\\times d\\) linear program in O(min(m 2,d 2)) expected number of pivot steps"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4045040"}},"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":"Q1100853$600E0756-43A5-400A-9345-73CF050CC7A0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"32400bd16e0d3c9e890c42120da825bb3ad96beb","datavalue":{"value":{"text":"A simplex variant solving an m\\(\\times d\\) linear program in O(min(m 2,d 2)) expected number of pivot steps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1100853$CA5465E1-4D73-4189-A2B7-CD4F74886DC6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4d7db4bba2337efb62f78a14ada84d41f0196d87","datavalue":{"value":"0641.65054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100853$8C904686-7889-4B08-B5AB-19BAB93935F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b3657642f2a29fb63e6917e8481d490caa593e6","datavalue":{"value":"10.1016/0885-064X(87)90007-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100853$D79DF932-98C9-443C-8C7C-C5FAA079BE7E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e67ca2a650174f2842d7d36cd56e5d60bb320647","datavalue":{"value":{"entity-type":"item","numeric-id":344958,"id":"Q344958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$19003E7C-1A33-4A7A-970A-2F71FC8EADD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7f03cf6abbdf2fe79063aacbf005af333537b97","datavalue":{"value":{"entity-type":"item","numeric-id":619905,"id":"Q619905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$C5D186D1-B20D-4455-9DCE-5F4FC523DEBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c86f85759000edd4a75c5506bbb76118e6ada90c","datavalue":{"value":{"entity-type":"item","numeric-id":214970,"id":"Q214970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$59A71AB4-371C-4FF2-814C-3277E7D8C2FC","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":"Q1100853$4DE84715-F3E0-402B-854B-9664F12F9558","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1100853$5FFE7036-6D6B-445D-959D-65672818C0D0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"01652f14637a929411531bbc44af48391408bd13","datavalue":{"value":"The authors consider a linear program with m inequality constraints and d variables. Assuming a fairly general probabilistic distribution of the problem data they obtain the result that a variant of a simplex method, the parametric constraint-by-constraint algorithm, requires on the average at most 2(min(m,d)1) 2 pivots to solve the problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100853$15D325DF-2FF7-444A-ABE7-E7A3FE9F60C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100853$8DEB94A5-D50C-4BAD-9CA0-71631CA57D4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100853$30EC95B1-DFE3-44F8-90F7-E0336EA1F933","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a2cccf0d0de3a29f7867f1e1f66c18e373d70166","datavalue":{"value":"4045040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100853$097857DE-06CA-4E4C-BC61-820EC6DB8893","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6c91348980f3de5d09505b1e7afe5727fc7be33","datavalue":{"value":"expected number of pivot steps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100853$F3E29FF5-F1DC-4D65-89A8-C5ACB3E31176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100853$744D01F3-7BBC-4EFC-A53E-DB677E1FBD3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6a9e644a062c5b7767e4219356e03dc48d7fb21","datavalue":{"value":"simplex method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100853$BA8F13B6-4A31-4335-A4D7-E7DF4F0DE925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccb5437dfeddef26f838a0fcf2353913b6044838","datavalue":{"value":"parametric constraint-by-constraint algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100853$3CA62729-0722-418D-AF09-AF90A5B03E59","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"97b11b22685e207c4d337adfd6207079f4a27111","datavalue":{"value":"Q60307346","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100853$7F285084-C10C-4DF8-A7C1-C8BF5A7BD3CD","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":"Q1100853$7CD902B0-1FD8-4D0B-B822-7BD2A9181E71","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"50140f4e16cd721027e69ae62b1ef2adfb766b8a","datavalue":{"value":{"entity-type":"item","numeric-id":3755232,"id":"Q3755232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$0FB93729-93E3-48AD-84D3-05D7972A26F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40401a897fe57ab9b9ff536a3b097703c89d39b5","datavalue":{"value":{"entity-type":"item","numeric-id":3773194,"id":"Q3773194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$F0192330-4986-4C62-A41B-9A999905656F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b42f3dc512e24dd1fb1819b2c01512e3c7941b33","datavalue":{"value":{"entity-type":"item","numeric-id":3710288,"id":"Q3710288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$D6324E60-9DB1-4F4C-92F3-6C60EC62458A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed8c2c1fdf717202a8b7e746ac8be1d0089bc0eb","datavalue":{"value":{"entity-type":"item","numeric-id":3964318,"id":"Q3964318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$C51A8EC6-1CC9-4CB2-8FBB-D9ED48B4E760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1d6548487b304347f76272be92a6aa58d1c2a2","datavalue":{"value":{"entity-type":"item","numeric-id":3950310,"id":"Q3950310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$BE0926FA-38B6-4963-8AA3-CBCC7A366B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43ca27cba6b8cbde68d00987a946f9cde333444","datavalue":{"value":{"entity-type":"item","numeric-id":3844775,"id":"Q3844775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$5F2D13A7-2B49-464E-9958-440320A94829","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12086856e478cd73734a7548be2a18f4ec58d978","datavalue":{"value":{"entity-type":"item","numeric-id":2558159,"id":"Q2558159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$FC0EB842-250A-4728-8757-E9C41E39F4F6","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":"Q1100853$186E6AE4-CC60-45D1-A125-7C60B33A146A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88c255f2e6ecd34a611f1ccf928bf197acbeea63","datavalue":{"value":{"entity-type":"item","numeric-id":4051879,"id":"Q4051879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$05D2A231-2815-4950-A262-D9510A0D7EEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2112033775f243deea52f9a486bc33be0b852d10","datavalue":{"value":{"entity-type":"item","numeric-id":5332463,"id":"Q5332463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$CE89BA61-BA41-4CB9-A98F-B0F93B4330FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42d4aa61234160d73161e7b5cbbee87be4dc0fbc","datavalue":{"value":{"entity-type":"item","numeric-id":3953557,"id":"Q3953557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$A79F2FCF-9EBB-4C16-B86B-761D3B53E790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48f35a4ceb9ee73360ccff210994323058e8d3f7","datavalue":{"value":{"entity-type":"item","numeric-id":5187071,"id":"Q5187071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$718B744A-5B9F-4A43-8D90-1A26576FFC12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18df631356898e79cef527458a67d59a3d778e9a","datavalue":{"value":{"entity-type":"item","numeric-id":3755229,"id":"Q3755229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$93DFC6CE-9369-4D2B-B9D7-0E0F563277EB","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":"Q1100853$A6D38E5A-0063-422C-8F2D-2248BEE18358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b2f7e9f8d77a5f5e1e1301aea35f7ce1c6a09d","datavalue":{"value":{"entity-type":"item","numeric-id":3346084,"id":"Q3346084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100853$245C179A-D540-4FF8-BF94-9131C9B08BEA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d8274b0a85c436d8ccfc5853381dd439a6762b39","datavalue":{"value":"https://doi.org/10.1016/0885-064x(87)90007-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1100853$253E40D4-3D38-4914-B92D-3EDEBEA0F74F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ee74dfb0ebb7ae418f49e1b5ae3d1b6bfbbd813c","datavalue":{"value":"W2021495277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100853$DCA02BF6-DAA8-4F42-93D3-9113086E177A","rank":"normal"}],"P1643":[{"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":"2389269e67152eab0495ab2753044cb0d88d69b2","datavalue":{"value":{"amount":"+0.9202300310134888","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":"Q1100853$CBA4DC1A-D3E9-4BCD-903F-6E9067CA8475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73311c5fcf73a6f5f49d9077888220e3298f79a8","datavalue":{"value":{"entity-type":"item","numeric-id":3337215,"id":"Q3337215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2961682109a718525b901a6ded24ec05bbdffdd8","datavalue":{"value":{"amount":"+0.8566359877586365","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":"Q1100853$71A1164A-5E28-4DFA-98C1-1419A332B3CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cf30225d4964c9021a4e17a87b5503a2d2fc551","datavalue":{"value":{"entity-type":"item","numeric-id":3710288,"id":"Q3710288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c68207e3ebe728d1827c1548ed500fbc2725d934","datavalue":{"value":{"amount":"+0.8545123338699341","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":"Q1100853$2319965F-6065-4E81-9504-A263ED7E1CC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40e48da266b26192d0bc6ca4a0d047cc32bcf23d","datavalue":{"value":{"entity-type":"item","numeric-id":3773194,"id":"Q3773194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32bdd470a6d34ba0bc8b355894f1d54ad3388400","datavalue":{"value":{"amount":"+0.8502052426338196","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":"Q1100853$0D6924E2-CA9D-4202-A65C-F280ABAF5165","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d8e18ac83b7f08720829d5c6584fecaf19b9b12","datavalue":{"value":{"entity-type":"item","numeric-id":3346084,"id":"Q3346084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18b3be690410d9942cb5ac472a728bf95810d0ed","datavalue":{"value":{"amount":"+0.8435280919075012","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":"Q1100853$952FE4A1-D946-470A-B1EA-B13DD874FBF0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A simplex variant solving an m\\(\\times d\\) linear program in O(min(m 2,d 2)) expected number of pivot steps","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_simplex_variant_solving_an_m%5C(%5Ctimes_d%5C)_linear_program_in_O(min(m_2,d_2))_expected_number_of_pivot_steps"}}}}}