Improving complexity of Karmarkar's approach for linear programming

Abstract

In this paper, we are interested in the performance of Karmarkar's projective algorithm for linear programming. Based on the work of Schrijver, we offer a new displacement step better than Schrijver's one which led to a moderate improvement in the behavior of the algorithm shift. We show later that the algorithm converges after \(\frac{n}{1-\log\left( 2\right) +(\frac{nr^{2}}{10})}\log\big( \frac{c^{t}e_{n}}{\varepsilon}\big) \) iterations. This purpose is confirmed by numerical experiments showing the efficiency of the obtained algorithm, which are presented in the end of the paper.

Keywords

• linear programming
• interior point method
• potential function