Towards an asymptotic analysis of Karmarkar's algorithm (Q580169): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(86)90134-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2037650903 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new polynomial-time algorithm for linear programming / rank | |||
Normal rank |
Latest revision as of 11:16, 18 June 2024
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