{"entities":{"Q811094":{"pageid":812942,"ns":120,"title":"Item:Q811094","lastrevid":49552180,"modified":"2026-01-07T17:13:37Z","type":"item","id":"Q811094","labels":{"en":{"language":"en","value":"A potential-reduction variant of Renegar's short-step path-following method for linear programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4215284"}},"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":"Q811094$5962EBC8-69BB-4BC2-B441-764A6219E9D4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1f396c9e20ffc922c819a7bf4bbd475264e512ac","datavalue":{"value":{"text":"A potential-reduction variant of Renegar's short-step path-following method for linear programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q811094$D8418D58-C993-449B-B837-2459A223D1E3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2d606b0446b5be8f4eb4c58d52fccdcd9e288eee","datavalue":{"value":"0734.65050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811094$435C32BE-D203-49F9-B2CB-24123A9EA010","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"87034f8c0c9200d33f1cbbbbca3712f2a8c5534c","datavalue":{"value":"10.1016/0024-3795(91)90266-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811094$3F49874D-AD96-467C-9E26-D778B6640BCB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$F60B3365-5706-4C09-83A9-4F9DA1EAC467","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q811094$F218F6DF-339C-4B4C-9B44-198F476361F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"366e17de3697e15fe931664932664d8f5bedffc7","datavalue":{"value":"The authors propose a new polynomial potential-reduction method for linear programming. This method can be interpreted as a large-step pathfollowing method. A line search is performed along the Newton direction with respect to \\textit{J. Renegar}'s strictly convex potential function [Math. Program, Ser. A 40, No.1, 59-93 (1988; Zbl 0654.90050)] if the iterate is far away from the central trajectory.    In the other case the lower bound for the optimal value will be updated. Depending on this updating scheme, the iteration bound is proved to be O(\\(\\sqrt{n}L)\\) or O(nL). The method differs from the previous potential- reduction method in the choice of the potential function and the search direction.","type":"string"},"datatype":"string"},"type":"statement","id":"Q811094$EEB1C48F-B7D8-4476-9C62-52ADC0B7C7D2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811094$8C950002-AB40-455D-A5BC-05D62B553B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811094$B2B5B957-2CC4-4A64-9246-DA557B305665","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"794d029caaab3384f74cd7171e0864fa4bf45618","datavalue":{"value":"4215284","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811094$6719E3DB-B81C-40CE-8FEC-F38C3B4440E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"597d725a93d08251d054704b08f0c69b5e3df8bd","datavalue":{"value":"polynomial potential-reduction method","type":"string"},"datatype":"string"},"type":"statement","id":"Q811094$3621803C-356B-41B0-9ECB-F01EBCDC94F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q811094$E2AC8417-254F-4131-B550-59ECBC6CDB92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a311afff9c4907820fa757823a71654fe7ed8747","datavalue":{"value":"large-step pathfollowing method","type":"string"},"datatype":"string"},"type":"statement","id":"Q811094$00E52B64-A993-4B48-88ED-5DC870834212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d29ab8b57f7ba662728a4122498bb0b711727713","datavalue":{"value":"line search","type":"string"},"datatype":"string"},"type":"statement","id":"Q811094$7B8F8D08-6915-4C94-BA0F-6A0C6D0F6E02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1df8d6c0f4a14cdc4572e1f09ee94b91974e504a","datavalue":{"value":"Newton direction","type":"string"},"datatype":"string"},"type":"statement","id":"Q811094$D7938AA7-8F70-4A39-AAFF-6EF11C3DD1A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be8ddcd6dc1ae334dc3ada711d40958057ff5c76","datavalue":{"value":"iteration bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q811094$90CFDE81-98F6-419E-9D32-BAE03A996F31","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bd16349daa320c4b168114d45d7d9b42ad4a22b2","datavalue":{"value":"Q114852085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q811094$BA3AC59D-0C68-4487-89E9-2DC78AA37BD6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c6b33790e0c6a8f0e049ecc7a550a5d64abb0c10","datavalue":{"value":{"entity-type":"item","numeric-id":344966,"id":"Q344966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$5668C8E4-0D8D-4458-86E7-FE57A11C8A86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41f9223d98cb24b639031125780dec8c6cadee10","datavalue":{"value":{"entity-type":"item","numeric-id":172146,"id":"Q172146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$F9CC06A9-2EE4-423A-B237-173DDE601B23","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":"Q811094$4A748C26-61AE-494B-82D0-8E84671E0E2E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"92db2f56f743ab9e3d7f512e40308a0b85c6b78a","datavalue":{"value":{"entity-type":"item","numeric-id":586366,"id":"Q586366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$3BC40161-163B-4579-8AAB-B9C1517D8C14","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":"Q811094$5824DB78-4CAF-470A-9996-C5BD466ABC35","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c712c4d3595da4dd5e7b0dcde6b07d4ae6533ba3","datavalue":{"value":{"entity-type":"item","numeric-id":1181912,"id":"Q1181912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$A001D12C-40E9-44A5-A9CF-A5A96F006A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef37f284637204ddf1842033032a153dd2ddd1d0","datavalue":{"value":{"entity-type":"item","numeric-id":4012424,"id":"Q4012424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$5C63F441-B16E-4F39-BE24-2349CFEDACF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c98bc796268099d123821888c91fd765bb4a5f97","datavalue":{"value":{"entity-type":"item","numeric-id":4012425,"id":"Q4012425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$E52BD006-5C26-424B-A567-37CFA16F50D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75f022ddc101250b64e660b1ee59fb77fe202328","datavalue":{"value":{"entity-type":"item","numeric-id":4735039,"id":"Q4735039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$E91B3A11-22E8-4827-99DE-705B75220DB6","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":"Q811094$B68EFD97-ED34-4D59-89B0-04E4B21F07C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53d400ae67354c276eb452acdccfbc71361c8b32","datavalue":{"value":{"entity-type":"item","numeric-id":1108927,"id":"Q1108927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$4E97B18F-5444-43DC-8510-8A16C2E7C7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe19405d38d4020145083899ea9f1ee49ed92523","datavalue":{"value":{"entity-type":"item","numeric-id":3494376,"id":"Q3494376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$971597A9-7582-4A63-8759-1330239FCAA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0645fdaa8941523699beeacef604bd643337295","datavalue":{"value":{"entity-type":"item","numeric-id":920841,"id":"Q920841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q811094$3DCB29FC-EAA3-4DC3-AF7C-FD7CB3209A79","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b37bb00ee3147494b25a9d47e918d549f09c0797","datavalue":{"value":{"entity-type":"item","numeric-id":4012425,"id":"Q4012425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a194cac62f7e54c8be7e0becd9d5039df02f2f35","datavalue":{"value":{"amount":"+0.8968374133110046","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":"Q811094$1EB53204-70A7-4C4C-B116-3CA768AF9944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7286b46e84b7b482df8871b67bb5e2d8f4eb2d3","datavalue":{"value":{"entity-type":"item","numeric-id":5202843,"id":"Q5202843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f07552db4dcd1094f60335c46a888a980982a0b","datavalue":{"value":{"amount":"+0.853586733341217","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":"Q811094$9F21C84E-241A-4608-B79B-0AADA1FE0B0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2308ac3236f4d6176a52a316ff1a7d3b4037c06b","datavalue":{"value":{"entity-type":"item","numeric-id":811360,"id":"Q811360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ad14074b4d2658abb5c4f331d97252586af1900","datavalue":{"value":{"amount":"+0.8520569801330566","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":"Q811094$8A331009-FFA0-47EF-BB0D-10B310697C33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a61ad2fd48699b8b1b05e009ed7fe1cb5ccb26d","datavalue":{"value":{"entity-type":"item","numeric-id":1361104,"id":"Q1361104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"943253145f93feed5eb51dfc88c0c6b323ce1b65","datavalue":{"value":{"amount":"+0.8488810062408447","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":"Q811094$4FF38900-B0AB-4289-B19F-F0711534CECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac375fd28534724c0e89996b234a8c1f4c331b7a","datavalue":{"value":{"entity-type":"item","numeric-id":805163,"id":"Q805163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f70a10f32b8802983780bdcf172bd7ce5ff5c91","datavalue":{"value":{"amount":"+0.8346565961837769","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":"Q811094$50AABE96-0492-49DC-A355-F5C255CC4B4E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:811094","badges":[]}}}}}