On the Performance of Karmarkar's Algorithm
本文介绍了Karmarkar算法的核心特点，并报告了数值实验结果，显示该算法迭代次数远少于单纯形法但计算时间更长，仅在利用问题结构时偶尔更快。
A new polynomial-time algorithm for linear programming was announced by Narendra Karmarkar of Bell Laboratories in 1984. This algorithm is claimed by Bell Labs significantly to outperform the simplex method. Many numerical experiments have been carried out by other workers in the field which show a much smaller iteration count than the simplex method but larger computational times. Some have shown that, by using advanced numerical linear algebra and heuristics to exploit the problem structure, it is possible occasionally to beat the simplex method even in terms of computation time. A brief description of the main features of Karmarkar's algorithm is presented, along with the results of some numerical experiments. Another closely related interior-point method which involves the rescaling of the variables is also discussed, and some details of the sparse matrix manipulations involved in an implementation of the algorithm are mentioned.