A proof of the polynomiality of the Iri-Imai method (Q1260658)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A proof of the polynomiality of the Iri-Imai method |
scientific article; zbMATH DE number 370454
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A proof of the polynomiality of the Iri-Imai method |
scientific article; zbMATH DE number 370454 |
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
