Improving complexity of Karmarkar's approach for linear programming

Authors

  • Djamel Benterki Université Sétif-1
  • Mousaab Bouafia Université Guelma

Keywords:

linear programming, interior point method, potential function

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.

Downloads

Download data is not yet available.

References

N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), pp. 373--395, http://dx.doi.org/10.1007/BF02579150

A. Keraghel, Etude adaptative et comparative des principales variantes dans l'algorithme de Karmarkar, Dissertation thesis, Université Joseph Fourier, Grenoble, France, 1989.

A. Keraghel and D. Benterki, Sur les performances de l'algorithme de Karmarkar pour la programmation linéaire, Revue Roumaine des Sciences Techniques-Mécanique Appliquées, 46 (2001) No. 1, pp. 87-96, http://www.imsar.ro/html/journals.html

I.J. Lustig, A practical approach to Karmarkar's algorithm, Technical report sol 85-5 Systems optimization laboratory; Dept. of operations research. Stanford. Univ.; Stanford California 94305, 1985.

R. Naseri and A. Valinejad, An extended variant of Karmarkar's interior point algorithm, Applied Mathematics and Computation 184 (2007), pp. 737-742, http://dx.doi.org/10.1016/j.amc.2006.05.196

C. Roos, T. Terlaki and J. Vial, Optimization Theory and Algorithm for Linear Programming Optimization, Princeton University, 2001.

A. Schrijver, Theory of linear and integer programming, John Wiley & Sons, New York, 1986.

Downloads

Published

2014-08-01

How to Cite

Benterki, D., & Bouafia, M. (2014). Improving complexity of Karmarkar’s approach for linear programming. Rev. Anal. Numér. Théor. Approx., 43(2), 159–167. Retrieved from https://ictp.acad.ro/jnaat/journal/article/view/2014-vol43-no2-art5

Issue

Section

Articles