A proof of the polynomiality of the Iri-Imai method (Q1260658): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jcom.1993.1018 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1991904536 / rank | |||
Normal rank |
Latest revision as of 02:31, 20 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