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

• Pagination: 22P
• Serial:
  • CENTRE DE RECHERCHE SUR LES TRANSPORTS - PUBLICATION
  • Issue Number: 403
  • Publisher: CENTRE DE RECHERCHE SUR LES TRANSPORTS - UNIVERSITE DE MONTREAL

Subject/Index Terms

• TRT Terms: Calculation; Linear systems; Methodology; Planning
• Uncontrolled Terms: Modifications
• ITRD Terms: 6464: Calcul; 9102: Methode; 9048: Modification; 143: Planification; 6484: Systeme lineaire
• Subject Areas: Planning and Forecasting; I10: Economics and Administration;

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