{"entities":{"Q1260658":{"pageid":1271408,"ns":120,"title":"Item:Q1260658","lastrevid":67385397,"modified":"2026-04-12T17:16:17Z","type":"item","id":"Q1260658","labels":{"en":{"language":"en","value":"A proof of the polynomiality of the Iri-Imai method"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 370454"}},"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":"Q1260658$284CC015-EAA8-467A-8E29-6026DD024E3F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff2708372738d4fc82659db33a97dd7ad8e0824c","datavalue":{"value":{"text":"A proof of the polynomiality of the Iri-Imai method","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1260658$5A0F9115-A4D5-4EFB-B268-DD130FA4EA58","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f38771b171f9ee6829c6fd5c6a4c063c52f628f","datavalue":{"value":"0811.90066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260658$63762600-6173-4A29-B09E-A9C1BAA6E9C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d247353974e86e1b3842738b51f9a3ac8e59fae0","datavalue":{"value":{"entity-type":"item","numeric-id":749242,"id":"Q749242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260658$A0DA574A-209D-45FB-AD9C-ABCBD3E1054D","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":"Q1260658$691F11AB-D805-4819-BF12-C7B561714FBE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63a2a2109a0646bfe8e8a3130f00ca3f280d500e","datavalue":{"value":{"time":"+1993-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1260658$D939F0C2-5724-42A0-A09F-C747EB157350","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e5ef3c57840fa0d4c17ff632b01ace122a2d3a74","datavalue":{"value":"The paper gives an improved polynomiality proof of Iri-Imai's multiplicative penalty function method for linear programming problems establishing the same time complexity bound Kamarkar's original method has. The proof techniques used to estimate the upcoming Newton vectors of the method allow an extension to quadratic programming problems, which is described in the second half of the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260658$E0A09866-FA78-4D69-BAAE-A9EF8E36A370","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260658$1FEB40EA-291D-4944-B832-6365C3CB9B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260658$FC39A7AC-DDE9-48A8-A6E2-4051B7A1CF6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260658$FC1F588A-B774-475C-851C-277B8219278B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae44b5c251d9921ef5937dd2f52c69d55f27aa11","datavalue":{"value":"370454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260658$A0A43E4D-77F4-4494-B648-52508D8680FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5463f8cb67c335ff66aa835d1eefbd219fa938e5","datavalue":{"value":"interior point methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260658$70F38866-20FD-4A75-89C3-29787BB6D21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3ed23eab002ac34be49ed5615cb47cb376eede3","datavalue":{"value":"polynomiality proof","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260658$49500F48-6BA2-41AE-9382-E070C7FE03B2","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":"Q1260658$7BA18364-E785-4AB8-8E74-C07F4E2C8D7B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dec899fb6cb7937660b5894e6d69cdf7cde57bf6","datavalue":{"value":"https://doi.org/10.1006/jcom.1993.1018","type":"string"},"datatype":"url"},"type":"statement","id":"Q1260658$1C79687A-9DA7-498D-B8D7-01C0E6F80596","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c6c673fa8ef19b6be71fa1edb08110d676a2c285","datavalue":{"value":"W1991904536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260658$15066F7B-86E4-4BC6-A960-7ABEE48B226A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a09a848596fb547540ca59b10da89c3b2a8d836a","datavalue":{"value":"10.1006/JCOM.1993.1018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260658$D58DFF0B-BC81-4E4E-A165-2816EF0BD329","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd4e209310c3f5f2c968ef083ae8254dc2f8fd4c","datavalue":{"value":{"entity-type":"item","numeric-id":1915925,"id":"Q1915925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"049905b13559d79c61889080d2da6ffcd2ab3fd0","datavalue":{"value":{"amount":"+0.8256949186325073","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":"Q1260658$9B789DA6-E409-42CB-9E5A-C74657BA8DA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ae421163053d63dcf6f360344c565d133ff6b68","datavalue":{"value":{"entity-type":"item","numeric-id":1824548,"id":"Q1824548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d348f5063a6855d1ad34d5c11c2a86a4be4a15cc","datavalue":{"value":{"amount":"+0.7960063815116882","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":"Q1260658$053633F5-3154-4EBB-A5D5-B9BA50834A53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9aa49de136036388829e21563be76fbc3a10eac1","datavalue":{"value":{"entity-type":"item","numeric-id":3757681,"id":"Q3757681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eec608c085e338f87c6ab3dc7075d32b18a062d","datavalue":{"value":{"amount":"+0.7935847043991089","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":"Q1260658$F7314178-4097-4DD4-AF71-6703D499092C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afe8669c32744da2e5fa778fcbebd9e2843dca8a","datavalue":{"value":{"entity-type":"item","numeric-id":3793937,"id":"Q3793937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd121fcb26d4c68c69809849de2c76d3ea404bd3","datavalue":{"value":{"amount":"+0.7910852432250977","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":"Q1260658$119ECCE0-E723-404E-ADB6-9CCEBC95F698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227deaa95037332d3a63fc36375c496cf8356307","datavalue":{"value":{"entity-type":"item","numeric-id":3474482,"id":"Q3474482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8524cbdd7d529fce3d9dc58f4c22e9eca9fbe91","datavalue":{"value":{"amount":"+0.7862336039543152","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":"Q1260658$B939DE46-B14E-40E6-95E4-A0E86DB0CEA4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A proof of the polynomiality of the Iri-Imai method","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_proof_of_the_polynomiality_of_the_Iri-Imai_method"}}}}}