{"entities":{"Q5942223":{"pageid":8119025,"ns":120,"title":"Item:Q5942223","lastrevid":97649843,"modified":"2026-06-05T15:10:07Z","type":"item","id":"Q5942223","labels":{"en":{"language":"en","value":"Complexity of the gravitational method for linear programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1638133"}},"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":"Q5942223$6664CB76-1B81-4F4B-ADF9-C58E562D38B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f19c54282932099cb26ab8cbb5ccaa833021916a","datavalue":{"value":{"text":"Complexity of the gravitational method for linear programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5942223$D807C2DD-68F7-4491-BA94-63BFDA881306","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f02fc6cc972a3028a5e46605e9d16395b1640732","datavalue":{"value":"1016.90024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942223$9163E3E9-919F-4F73-9195-7843E1C01AA2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c3a777083352c285939226b1bd312b3b00ea67e3","datavalue":{"value":"10.1023/A:1017591509792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942223$77076584-A9F6-47F9-90CE-31990AF3D75C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a3c8bf4d8569c126380a9fc42f55609089e776fb","datavalue":{"value":{"entity-type":"item","numeric-id":82026,"id":"Q82026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$9956F04A-EBBA-4379-96E3-0D0A1824E36E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cf47f0c2f8921918b490b998264be36172ab63f7","datavalue":{"value":{"time":"+2001-08-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":"Q5942223$13F12A89-52EB-47A9-B59D-A551F0BF70E8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5596b41a1bc4ec41f2df874f0e4b345b2f411b45","datavalue":{"value":"The gravitational method to solve a linear program starts by dropping a particle from an interior point of the polyhedron and letting it move under the influence of a gravitational field parallel to the objective function direction. After hitting the boundary of the polyhedron, the particle moves on the surface along the steepest-descent feasible direction, eventually arriving at an optimal solution. It is shown that this simplex-like algorithm needs exponentially many iterations in the worst case. A class of linear programs with \\(n\\) variables and \\(2n\\) constraints is constructed in which the above algorithm behaves like the simplex algorithm after the boundary is reached and \\(2^n-1\\) vertices will be visited; the input bit complexity is \\(O(n\\log n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942223$40DA8947-DD53-420B-A496-724B0C314325","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7b5216524182c05be49019414dd0cdfe4dc64711","datavalue":{"value":{"entity-type":"item","numeric-id":333094,"id":"Q333094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$D41DBD8D-83A3-4A16-957F-3F7977233793","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942223$D5CEB5FA-DC65-4CAA-BBF9-9FDCE8E2D166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942223$1D4D94C5-9896-4C69-82A8-3FCE5B8AEDB2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cf984f1c7f41e41e869284ca9d2e163d3e7f91cc","datavalue":{"value":"1638133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942223$D820A567-9765-4AFA-90C8-E94A863538EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6a9e644a062c5b7767e4219356e03dc48d7fb21","datavalue":{"value":"simplex method","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942223$121D00DA-E93E-4B40-AC97-72C682F80E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942223$8346E668-F676-4819-8F4F-607BA0D94412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14f5692e185b1488dd97e357834d4b024a1d4fa4","datavalue":{"value":"worst-case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942223$D74E7A96-EE68-47F0-A9A4-F89F1CE09716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11f69f3fec10424135cfae54a1e308a8dbb796cd","datavalue":{"value":"gravitational method","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942223$F7EFC70E-E9D5-4ADC-9EFA-22DE9E145E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4901c88c254883d3f81ed98c588ea7267e35f73f","datavalue":{"value":"linear program","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942223$C5979F02-08C5-42BA-BB85-828354778825","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7a7d759f54463b3e2d5b451161c02d04f0bc3f5f","datavalue":{"value":{"entity-type":"item","numeric-id":20387,"id":"Q20387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$84910CFA-AD8B-46D1-AC4C-FB6788061C0A","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":"Q5942223$C853A3B8-A12F-4BCF-B122-35984CB7A879","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fd5a800ca63c2c7dea71b91a43d4ff68c64219d","datavalue":{"value":{"entity-type":"item","numeric-id":4165158,"id":"Q4165158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$CB0E5D58-927C-4326-924E-78CCCD1258ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d904f191988dbab1b9a99fc97fc9579b0699be9d","datavalue":{"value":{"entity-type":"item","numeric-id":4178772,"id":"Q4178772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$283FE303-CCA6-4B47-A7C6-53D0CDA33263","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":"Q5942223$868A6BBE-F352-49F0-B9F7-B48B6A0F3AA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52b41fc943eff77f7bb968813dba052cc6bd89f5","datavalue":{"value":{"entity-type":"item","numeric-id":5629405,"id":"Q5629405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$F082E3C1-78EE-4FD8-8DA3-D08338F5099A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ddfb236c59ba17c8b0a52a945a31feef7521935","datavalue":{"value":{"entity-type":"item","numeric-id":1134626,"id":"Q1134626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$A537EC90-DDE7-4B41-AE79-A41D4F9E5D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$6ED3B159-1E71-4033-BE23-7E56188E6DCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"822654aad4bf918a58ad623e1fe15afbccaed3dd","datavalue":{"value":{"entity-type":"item","numeric-id":3622260,"id":"Q3622260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$D8C0491F-B81D-4017-A93C-FEA98213CF19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a509c1a7890ace72659b56bea6039ed3541ff224","datavalue":{"value":{"entity-type":"item","numeric-id":3753810,"id":"Q3753810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$3ED864AD-BA4E-4FF9-AD7A-6841876FE787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8fea9a5dba7c0c825c98a79aa7f9c13491987b","datavalue":{"value":{"entity-type":"item","numeric-id":5547252,"id":"Q5547252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$E8520A6E-3943-42D7-A96E-F51AF85249A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c83d3ac1eb6f199086933e273cb1928bcf98889","datavalue":{"value":{"entity-type":"item","numeric-id":4005821,"id":"Q4005821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$C7CE6929-9424-4F66-B7B9-C6AFBE6CB586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eab77c5a7cbda207f53a33b3f2866b0e04e1689e","datavalue":{"value":{"entity-type":"item","numeric-id":1821685,"id":"Q1821685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$5A578E52-301F-40B1-9C5A-E54E276C5EBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ef194e3596a1cf44d19b1025b9f2273c2ad79f0","datavalue":{"value":{"entity-type":"item","numeric-id":583105,"id":"Q583105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$8E378FF2-0218-4C99-A257-F6F8C29842CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02c3cd6c628579d7eff4f0425b4e762eb1f8cd1","datavalue":{"value":{"entity-type":"item","numeric-id":4106692,"id":"Q4106692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$4D5AFAFA-3E76-4730-83DD-9BCC2E50FE5D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a75bbf93092284c5ac92c9c51ea4a6318f93c926","datavalue":{"value":"https://doi.org/10.1023/a:1017591509792","type":"string"},"datatype":"url"},"type":"statement","id":"Q5942223$580A837F-76F6-4DE4-A277-4398454BD309","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b59d156ada395af98bb4ecb2d718f0063c6fec83","datavalue":{"value":"W236210359","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942223$7A4AEC42-22C1-4A64-B82A-8DDF8602F7D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c12e289f7b4295a69d25b3f2f8c3ff746ad7b761","datavalue":{"value":{"entity-type":"item","numeric-id":714536,"id":"Q714536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$93DE6487-D877-435C-819F-6E91EC262842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbfd1fd05945d2748ff60570f3d46f9e18973328","datavalue":{"value":{"entity-type":"item","numeric-id":5865975,"id":"Q5865975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$A731A250-F421-4415-871D-01D50530DA05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef3537763bc61a3e5a550c32d0c322391198f208","datavalue":{"value":{"entity-type":"item","numeric-id":6567771,"id":"Q6567771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942223$B3538DA9-0917-45E1-98D8-37C82D62FCFB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a6a109f4072e44155dc80e66577f64a32f8df47","datavalue":{"value":{"entity-type":"item","numeric-id":1821685,"id":"Q1821685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b12a161686545ef4223361692c11a2e7bbe24dd","datavalue":{"value":{"amount":"+0.8525572419166565","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":"Q5942223$C5476BFA-1036-4CF9-AA93-ED95D6AB5AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49b53a4322bcacaa3f6765ab59d933a7c378a4d0","datavalue":{"value":{"entity-type":"item","numeric-id":583105,"id":"Q583105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c7686d68af5a2aa77d2522a941f5d71a827ee88","datavalue":{"value":{"amount":"+0.8385129570960999","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":"Q5942223$0C1D3D5C-93AA-4B4B-9E99-0D8D38A13696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c1ac8b0242a223f932069c6a77e38bd06e5bb1b","datavalue":{"value":{"entity-type":"item","numeric-id":4333297,"id":"Q4333297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e42b8e2f6616091bc129c9fab293b8c767023911","datavalue":{"value":{"amount":"+0.8143864870071411","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":"Q5942223$81367FC5-96E5-431A-92E1-5841257E40F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"961f8628ffab0964c29dba7fbb310d0924593c11","datavalue":{"value":{"entity-type":"item","numeric-id":3415351,"id":"Q3415351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88045e164d9f6fd149169cd1a4ca4396fbdedfd0","datavalue":{"value":{"amount":"+0.8063915967941284","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":"Q5942223$2AB0BE40-BB10-4594-BAA4-3730068C2AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bb626605b8ff08fad5742ef61af13e7f494a5ae","datavalue":{"value":{"entity-type":"item","numeric-id":2476413,"id":"Q2476413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e90efe376009f43932e06548d6a253f955bf092c","datavalue":{"value":{"amount":"+0.7983701229095459","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":"Q5942223$F6303698-9B58-493E-9FBA-B74434FCC084","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of the gravitational method for linear programming (scientific article; zbMATH DE number 1638133)","badges":[]}}}}}