A proof of the polynomiality of the Iri-Imai method (Q1260658): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:44, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A proof of the polynomiality of the Iri-Imai method |
scientific article |
Statements
A proof of the polynomiality of the Iri-Imai method (English)
0 references
24 August 1993
0 references
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.
0 references
interior point methods
0 references
polynomiality proof
0 references