A proof of the polynomiality of the Iri-Imai method (Q1260658)
From MaRDI portal
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
