L'ALGORITHME DE KARMARKAR

Ce texte presente les principaux resultats theoriques de l'algorithme de Karmarkar pour la programmation lineaire. La complexite de cet algorithme est polynomiale et requiert 0(n3.5LlnLlnlnL) operations en comparaison de 0(n4LlnLlnlnL) pour l'alogrithme ellipsoidal de Khachiyan, ou n est le nombre de variables et L est le nombre de bits en input. L'algorithme consiste en l'application repetee d'une transformation projective suivie de l'optimisation sur une sphere. Dans un but pedagogique, le detail de plusieurs demonstrations est donne. (A).

  • Authors:
    • DESROSIERS, J
  • Publication Date: 1986

Language

  • French

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01248072
  • Record Type: Publication
  • Source Agency: Institut Francais des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)
  • Files: ITRD
  • Created Date: Nov 20 2010 4:31AM