Improving complexity of Karmarkar's approach for linear programming

Djamel Benterki, Mousaab Bouafia

Volume 43,  2014

journal of Numerical Analysis and approximation Theory

https://ictp.acad.ro/jnaat/journal/article/view/2014-vol43-no2-art5

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 n1−log(2)+(nr210)log(ctenε)n1−log⁡(2)+(nr210)log⁡(ctenε) 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