Towards an asymptotic analysis of Karmarkar's algorithm (Q580169): Difference between revisions

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.