{"entities":{"Q1340070":{"pageid":1350809,"ns":120,"title":"Item:Q1340070","lastrevid":70184592,"modified":"2026-04-13T13:01:25Z","type":"item","id":"Q1340070","labels":{"en":{"language":"en","value":"Polynomiality of infeasible-interior-point algorithms for linear programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 700817"}},"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":"Q1340070$308B8491-CF17-4D9A-985B-B99D02B2A901","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d9cd02391a227d9c4e5786963a5d771881b69d30","datavalue":{"value":{"text":"Polynomiality of infeasible-interior-point algorithms for linear programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1340070$98D6858B-EE12-4545-B184-C8477A34288D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0effeddbc4371031c99465c1645bb3726b5581f3","datavalue":{"value":"0828.90086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340070$8C700804-F5E9-43CD-8A12-DCC983D3696B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d1af4140a674cc7eb0cc8998249c12ec95d0e1d5","datavalue":{"value":"10.1007/BF01582216","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340070$00353B16-7A07-4735-8134-795BDB5C69A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1387dcc5a7382e1f53324eee772fa1425baa2648","datavalue":{"value":{"entity-type":"item","numeric-id":173893,"id":"Q173893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$05CFFB9A-91C9-4EF4-8AD7-5F377E3F0FB0","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":"Q1340070$5D403735-052E-4962-BE8B-34E9F5A0DF24","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"10b8be3aaae04a8b6e1fb062263f34380fce1ca5","datavalue":{"value":{"time":"+1994-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1340070$4C78DF6C-9AE8-45EE-A0E0-C814E8601498","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"62958638451f99c98bf88324d9e109e7b7978699","datavalue":{"value":"An infeasible interior point algorithm for solving a primal-dual pair of linear programming problems finds approximate optimal solutions of the pair if both problems have interior points and detects infeasibility when the sequence of iterates diverges. Polynomial-time convergence of this algorithm under the assumption that both primal and dual problems have feasible points are proved. The author shows that a modification of the infeasible interior point algorithm ``solves'' the pair of problems in polynomial time, without assuming the existence of the LP solution. Furthermore, he develops an \\(O(nL)\\)-iteration complexity result for a variant of the algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340070$F78342C1-32B0-4088-81EF-5EA02345305F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340070$63F396DA-CBE1-480E-A9FE-1EAB5762C242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340070$AAC7C286-C602-429D-916B-FC1EFF8801DE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"34c0f33ba909765aba28a772d48cec20de778e90","datavalue":{"value":"700817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340070$371B70FF-ED6D-44D4-BF63-5131547BDAEA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42004088b981888c3a857bb5ad935de2a42289a6","datavalue":{"value":"infeasible interior point algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340070$0CC4986D-643A-4DC6-A09B-787521C31457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f03700724630db2b32de944b0e392588212f73a9","datavalue":{"value":"primal-dual pair of linear programming problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340070$E104F782-A25C-4815-AA01-DCD185D7D735","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":"Q1340070$2770651D-5860-4AE6-98CB-916B8330EF5A","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":"Q1340070$B3E24420-8AD0-4C09-A34E-5BBCB5AD5445","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ee0f6ae25a4ddf2f7ce519b32f3a280af283428","datavalue":{"value":{"entity-type":"item","numeric-id":1315419,"id":"Q1315419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$37EC30D3-C8EF-4D9A-8B14-0DAFAC70E04E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02a7afaa43720bcf86b29d1d0d8112e49edf9bd","datavalue":{"value":{"entity-type":"item","numeric-id":3491304,"id":"Q3491304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$D011A225-9CD0-46CC-99B2-241DA34468D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7887a1dbd123c34a453ce09ae845890c9ba820dd","datavalue":{"value":{"entity-type":"item","numeric-id":1123139,"id":"Q1123139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$0ABE812C-0FA0-4113-BAE0-22D8C7C7D534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04393c96542dcd8e82a6a803afd93e63a01c5f77","datavalue":{"value":{"entity-type":"item","numeric-id":803044,"id":"Q803044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$293F65F5-82E5-4168-B189-928CBFD63BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5595433e1d739ff967385f6abe4497bd290d31a7","datavalue":{"value":{"entity-type":"item","numeric-id":808184,"id":"Q808184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$606BC06F-172D-4816-BCD8-F5E01D893398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9bf10fa28d121c6da057f550b686f3b41c309f8","datavalue":{"value":{"entity-type":"item","numeric-id":4206561,"id":"Q4206561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$7BFFB3A4-5EAB-4420-9D30-45E2266C31AC","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":"Q1340070$1E7A3F34-1298-4A1A-A811-3DAD4B4B4A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d704b163797cf91f123edaacc228d2d912159b5","datavalue":{"value":{"entity-type":"item","numeric-id":1123121,"id":"Q1123121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$2216B0C3-11DA-4C89-A509-50F56A89AFDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5d2e319c9b5271cde3734ff2ddd89fa0c0a653c","datavalue":{"value":{"entity-type":"item","numeric-id":1123122,"id":"Q1123122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$B891168C-6AAD-4DFF-A044-3271520C092A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a99ea90c70a74fe1d8abbfbe33e5bf1641733b41","datavalue":{"value":{"entity-type":"item","numeric-id":4877503,"id":"Q4877503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$C9B9A160-1A6B-42B1-BAF1-C6872A5511BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4d2f64349cc7528ddcbda10cfea52985f701a54","datavalue":{"value":{"entity-type":"item","numeric-id":3804467,"id":"Q3804467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$C2E31E3F-EE2D-4179-9B20-655F1ADCC7F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0c9d2d6f2ddb30865cad743e8fd0d19f1096c1c","datavalue":{"value":{"entity-type":"item","numeric-id":4294753,"id":"Q4294753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340070$6E25AF0B-CCEB-4C5C-A6A5-B8D6DFA1776E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d445c738873a88f4c975860f70a08b9159e3379f","datavalue":{"value":"https://doi.org/10.1007/bf01582216","type":"string"},"datatype":"url"},"type":"statement","id":"Q1340070$8E6BD6CF-FD5F-4013-BA83-544E7B4B6B59","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ff31e1388a10389626768a9a3905f81780bf55fc","datavalue":{"value":"W1985332751","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340070$1256C1C4-D11F-4B1F-A510-D16BB4DDED2C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e495c2e2184ea523647f50adcecc7e5f4fb7544","datavalue":{"value":{"entity-type":"item","numeric-id":4253467,"id":"Q4253467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"252276efb998a9a423e338c14a7cc0acaaf6f952","datavalue":{"value":{"amount":"+0.8944974541664124","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":"Q1340070$6C01D425-85C2-4E0B-A79A-15518B04B296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b938df76ba1adf8ff71c16cb347864c5b1fa19e","datavalue":{"value":{"entity-type":"item","numeric-id":1572663,"id":"Q1572663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6e93c2921a64e1ccc97426bdde076d95bb9b8a2","datavalue":{"value":{"amount":"+0.8848429918289185","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":"Q1340070$06BF251E-D8D5-4DBE-B75D-6C137B65F6C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb7d84ebc70a92a3e6447aaaef8872f533cc4d1e","datavalue":{"value":{"entity-type":"item","numeric-id":4347845,"id":"Q4347845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"682fdc7069a73767918f1f15334ae223c3fbdc8f","datavalue":{"value":{"amount":"+0.8761899471282959","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":"Q1340070$729F935F-A7AA-4872-B549-E50878BF4B27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd3c3ea268173bfe0c3ca3f1a595f62e665a4833","datavalue":{"value":{"entity-type":"item","numeric-id":1915903,"id":"Q1915903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2867fbe64089092a3e461052d218e4384d70d91e","datavalue":{"value":{"amount":"+0.8662672638893127","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":"Q1340070$BB5C2478-0F88-4863-B73E-63F2A8975A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c454d5ed6c22da04138f53c560b80fa8f762ddf3","datavalue":{"value":{"entity-type":"item","numeric-id":4764308,"id":"Q4764308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb0d0896d8732bfba01e44d2b2bc48abbfc2d6c5","datavalue":{"value":{"amount":"+0.8606756925582886","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":"Q1340070$37D2BEB2-7473-4B73-B9E5-1743CC6C59A8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomiality of infeasible-interior-point algorithms for linear programming","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomiality_of_infeasible-interior-point_algorithms_for_linear_programming"}}}}}