Improving complexity of Karmarkar's approach for linear programming

Main Article Content

Djamel Benterki Mousaab Bouafia

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.

Article Details

How to Cite
Keywords
linear programming; interior point method; potential function
Section
Articles