Improving complexity of Karmarkar's approach for linear programming

Authors

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

DOI:

https://doi.org/10.33993/jnaat432-1026

Keywords:

linear programming, interior point method, potential function
Abstract views: 360

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 DOI: https://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 DOI: https://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. https://doi.org/10.33993/jnaat432-1026

Issue

Vol. 43 No. 2 (2014)

Section

Articles

License

Copyright (c) 2015 Journal of Numerical Analysis and Approximation Theory

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.