Towards an asymptotic analysis of Karmarkar's algorithm (Q580169): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| Property / review text | |||
The author states that \textit{N. Karmarkar}'s algorithm for linear programming [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] has generated excitement and controversy. Experimental results have been reported both supporting and refuting claims of substantial speed ups. The paper looks at the iterative process of Karmarkar's algorithm and gives a new proof of the number of iterative steps required by the algorithm in the worst case. Specifically, the proof identifies an explicitly geometric quantity that measures the algorithm's progress at each step. Analyzing the changing size of this quantity gives information about the dynamics of the algorithm. | |||
| Property / review text: The author states that \textit{N. Karmarkar}'s algorithm for linear programming [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] has generated excitement and controversy. Experimental results have been reported both supporting and refuting claims of substantial speed ups. The paper looks at the iterative process of Karmarkar's algorithm and gives a new proof of the number of iterative steps required by the algorithm in the worst case. Specifically, the proof identifies an explicitly geometric quantity that measures the algorithm's progress at each step. Analyzing the changing size of this quantity gives information about the dynamics of the algorithm. / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Rainer Beedgen / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 90C05 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 65K05 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 68Q25 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 4016588 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
worst case analysis | |||
| Property / zbMATH Keywords: worst case analysis / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
algorithm | |||
| Property / zbMATH Keywords: algorithm / rank | |||
Normal rank | |||
Revision as of 17:36, 1 July 2023
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Towards an asymptotic analysis of Karmarkar's algorithm |
scientific article |
Statements
Towards an asymptotic analysis of Karmarkar's algorithm (English)
0 references
1986
0 references
The author states that \textit{N. Karmarkar}'s algorithm for linear programming [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] has generated excitement and controversy. Experimental results have been reported both supporting and refuting claims of substantial speed ups. The paper looks at the iterative process of Karmarkar's algorithm and gives a new proof of the number of iterative steps required by the algorithm in the worst case. Specifically, the proof identifies an explicitly geometric quantity that measures the algorithm's progress at each step. Analyzing the changing size of this quantity gives information about the dynamics of the algorithm.
0 references
worst case analysis
0 references
algorithm
0 references
