{"entities":{"Q2476985":{"pageid":2487728,"ns":120,"title":"Item:Q2476985","lastrevid":73424556,"modified":"2026-04-14T15:54:43Z","type":"item","id":"Q2476985","labels":{"en":{"language":"en","value":"How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5248718"}},"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":"Q2476985$36AF92DD-9916-482A-A063-38BD8C42099E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dea48d899c3abea670bbe8df11b8cccba097a00d","datavalue":{"value":{"text":"How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2476985$635F9A92-7D6D-4CB6-B9B2-EAC205CDEE08","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3887eb2774d06c1fe4da16c3c9f7f64b7b148baf","datavalue":{"value":"1176.90394","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2476985$A6074D67-0FF3-4337-BFA5-467115D3E470","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"941735158b4cdc3c7c64344e4837f47a0e5a127d","datavalue":{"value":{"entity-type":"item","numeric-id":173841,"id":"Q173841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$6D54BE80-5CF0-450E-A527-2CF82383A0C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bdea860846a22eea3445fc2e0fc0dc1a0c3c53d","datavalue":{"value":{"entity-type":"item","numeric-id":941029,"id":"Q941029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$231DA835-B70D-4856-9E6C-422B4FB3DF70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5576e381cb70a9fb21eb731121e61c215fd1b7f","datavalue":{"value":{"entity-type":"item","numeric-id":172148,"id":"Q172148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$0194394A-16C4-4867-B052-6EEC8F1F84EC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$4989D482-446B-42C6-9FC0-A94AFA8AC878","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2bb6064fe12f1f98326de21fadc6a9704c90a","datavalue":{"value":{"time":"+2008-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2476985$95A3A61D-3A60-4C9B-BC39-0D6904A3C723","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b13e46258f6ea503f375bcf58ee63d53d8d8ab5c","datavalue":{"value":"\\textit{V. Klee} and \\textit{G. J. Minty} [in: Inequalities III, Proc. 3rd Symp. Los Angeles 1969, 159--175 (1972; Zbl 0297.90047)] gave an example for which the simplex method takes an exponential number of iterations. By refining a variant of the Klee--Minty example, the authors exhibit a nearly worst-case example for path-following interior point methods. It has been proven that solving this \\(n\\)-dimensional linear optimization problem requires at least 2 of power n minus 1 iterations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2476985$F87C4E79-D869-4E21-88D5-1691A6A31E84","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2476985$F2029037-61BD-45F2-A67B-92EF2B2E31E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4ac3edbc9a781214f87fc7c9c04c2c17e13b7ca7","datavalue":{"value":"90C51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2476985$A44B227E-B1F6-4D0B-BF12-CEF7E05ACC2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2476985$4A029246-A0E0-493C-A499-C886A1DE097B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2d122ac013d82f38d9a5f975e7ea52d2ba5ac784","datavalue":{"value":"5248718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2476985$C51C401F-E915-4EC4-9BDC-179DA90DC8DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2476985$3B88EB7A-BACA-45C3-B4DD-1FDE85DB6DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06b081ca97398e6e22b07f21a43ec8ba1e545222","datavalue":{"value":"interior point method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2476985$C9DE2E6A-F8A1-4287-A5CC-57AE6CE2BFBA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"01059bdcbc70020f351a0f9622de7706dbca9032","datavalue":{"value":{"entity-type":"item","numeric-id":589946,"id":"Q589946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$D8AB1BEE-410C-45CC-B3F1-62466FA1F05F","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":"Q2476985$A831124E-FA6B-4164-A61A-B0B64ED13DF3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5f747bd1890069690953c9e3be1ec7e0ddde936c","datavalue":{"value":"https://doi.org/10.1007/s10107-006-0044-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q2476985$CA204A68-EE73-4D3A-B87B-1737C29914C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"193e1ae6c335812c5d47dbb7beb52b83d479e019","datavalue":{"value":"W2056369327","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2476985$C90B3BA8-2C29-4B79-8FBB-6F7C9D6D9A04","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f5365de590f57490e4e910004dd8a4a1e9c0bb0","datavalue":{"value":{"entity-type":"item","numeric-id":3423600,"id":"Q3423600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$925A518D-3663-415A-B9C8-0260673B6BC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cda76caac7a26fb7b4d8da45ae01f2ceeec8dea3","datavalue":{"value":{"entity-type":"item","numeric-id":935228,"id":"Q935228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$1AB1CCEF-AF2C-449E-A581-C20DEA8031BF","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":"Q2476985$49E964E5-0A39-4C37-9B52-2A2908A47057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$132BF6A1-864D-4477-9EE5-42C6EDFE4180","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":"Q2476985$352749C2-9771-4545-947D-BFCC43778F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb6fd038d0b9c82fb0dcfe34afdd838bf0d5493","datavalue":{"value":{"entity-type":"item","numeric-id":3830814,"id":"Q3830814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$86E6C88E-AB2C-4E1C-A217-9F0331C147BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8725e208cda391fc2edbec00cb1dde4aaee29aa1","datavalue":{"value":{"entity-type":"item","numeric-id":4339096,"id":"Q4339096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$C4EE0A4E-693E-4C5D-8D31-566545382799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e5c1a00f23ab0b0dad7ec2aec30d058e08fa6d","datavalue":{"value":{"entity-type":"item","numeric-id":1312760,"id":"Q1312760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$54503323-9886-4CAC-9871-07FA7AB3D068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbb8ef99b7afaccdb065eed7109dc2a5a4c9e5dc","datavalue":{"value":{"entity-type":"item","numeric-id":1915913,"id":"Q1915913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$CC198F5B-1DD9-40CA-A8F0-74CF87102354","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":"Q2476985$8834F004-388D-4FFB-95D7-BBC5DBC6542D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"474b7e5c0d8cf5a9b274bd233be63067711b4aad","datavalue":{"value":{"entity-type":"item","numeric-id":5691079,"id":"Q5691079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2476985$4A4DB693-3DE4-4223-9AE4-606E92647ED7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e5b3b8701f3ac0ac9c546026bcaf14c6daa8df44","datavalue":{"value":"10.1007/S10107-006-0044-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2476985$375914E3-6E24-4267-BA7A-AABE062D6021","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc61c0ded5dbbe2334ca4006e431bce2d6e9d676","datavalue":{"value":{"entity-type":"item","numeric-id":3565464,"id":"Q3565464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"386e2fef9bc028ce5e96f57ac4f4f2ba9a7d1c75","datavalue":{"value":{"amount":"+0.8426748514175415","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":"Q2476985$FD063AEF-A1B0-4166-A110-1899258F1D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc5f094461527392a9f06969893d0a31ec3d1603","datavalue":{"value":{"entity-type":"item","numeric-id":3423600,"id":"Q3423600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce2aec15ddb1837f83809fac8b09804c5bbda1b8","datavalue":{"value":{"amount":"+0.8218986392021179","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":"Q2476985$4C6187FF-843A-4A0E-8634-E3084126DD78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9d5ca6d7cdd23e2e6f39844671bb594fdaf43a6","datavalue":{"value":{"entity-type":"item","numeric-id":3622260,"id":"Q3622260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c0e48b67a4c0623a7d3c80662e32d186ad31d60","datavalue":{"value":{"amount":"+0.7844548225402832","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":"Q2476985$2791E2F3-B9CA-426E-B530-A4021FB730E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9274ac95c619e9c6c20d69479d3b713fc9f37fce","datavalue":{"value":{"entity-type":"item","numeric-id":2325239,"id":"Q2325239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc0d0f335c3d20dca08048c0342a5bbc8340eec5","datavalue":{"value":{"amount":"+0.7834979295730591","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":"Q2476985$DA2C1BC3-D774-478C-9779-5D27944BABDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab5d667433659f97f51f265a52e474360fad8bbe","datavalue":{"value":{"entity-type":"item","numeric-id":941030,"id":"Q941030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fea75f129b3e20e1f2225a9ab9bd024d2e2bbbc","datavalue":{"value":{"amount":"+0.7809708118438721","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":"Q2476985$284A693A-4E10-43E5-AF22-089A206B9F71","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/How_good_are_interior_point_methods%3F_Klee-Minty_cubes_tighten_iteration-complexity_bounds"}}}}}