Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice.

PropertyValue
dbpedia-owl:thumbnail
dbpprop:abstract
  • Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice. Where <math>n</math> is the number of variables and <math>L</math> is the number of bits of input to the algorithm, Karmarkar's algorithm requires <math>O(n^{3.5} L)</math> operations on <math>O(L)</math> digit numbers, as compared to <math>O(n^6 L)</math> such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus <math>O(n^{3.5} L^2 \ln L \ln \ln L)</math> using FFT-based multiplication. Karmarkar's algorithm falls within the class of interior point methods: the current guess for the solution does not follow the boundary of the feasible set as in the simplex method, but it moves through the interior of the feasible region and reaches the optimal solution only asymptotically.
  • L'algorithme de Karmarkar est un algorithme introduit par Narenda Karmarkar en 1984 pour résoudre les problèmes de programmation linéaire. C'est le premier algorithme réellement efficace qui résout ces problèmes en un temps polynomial. La méthode des ellipsoïdes fonctionne aussi en temps polynomial mais est inefficace en pratique. En posant <math>n</math> le nombre de variables et <math>L</math> le nombre de bits d'entrée de l'algorithme, l'algorithme de Karmarkar réalise <math>O(n^{3,5} L)</math> opérations sur <math>O(L)</math> bits à comparer aux <math>O(n^6 L)</math> opérations pour la méthode des ellipsoïdes. Le temps d'exécution de l'algorithme de Karmarkar est ainsi <math>O(n^{3,5} L^2 \ln L \ln \ln L)</math> en utilisant l'algorithme de Schönhage-Strassen. L'algorithme de Karmakar est une méthode du point intérieur : la solution candidate courante ne suit pas les bornes de l'espace faisable comme dans l'algorithme du simplexe, mais approche par l'intérieur de l'espace faisable et atteint la solution optimale de manière asymptotique.
  • L'algoritmo di Karmarkar è un algoritmo polinomiale per risolvere un problema di programmazione lineare. L'algoritmo di Karmakar utilizza un metodo a punto interno evitando accuratamente i vertici e ogni punto della frontiera della regione ammissibile nella ricerca del valore ottimo. L'algoritmo genera una successione di punti strettamente ammissibili che convergono verso il punto ottimale, il quale invece può essere un vertice. L'algoritmo ha un tempo polinomiale nella grandezza del problema anche nel caso che il problema sia illimitato: in questo caso si accorge della non esistenza di un punto ottimale e smette restituendo una garanzia della non limitazione del problema.
dbpprop:hasPhotoCollection
dbpprop:reference
rdfs:comment
  • Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice.
  • L'algorithme de Karmarkar est un algorithme introduit par Narenda Karmarkar en 1984 pour résoudre les problèmes de programmation linéaire. C'est le premier algorithme réellement efficace qui résout ces problèmes en un temps polynomial. La méthode des ellipsoïdes fonctionne aussi en temps polynomial mais est inefficace en pratique.
  • L'algoritmo di Karmarkar è un algoritmo polinomiale per risolvere un problema di programmazione lineare. L'algoritmo di Karmakar utilizza un metodo a punto interno evitando accuratamente i vertici e ogni punto della frontiera della regione ammissibile nella ricerca del valore ottimo. L'algoritmo genera una successione di punti strettamente ammissibili che convergono verso il punto ottimale, il quale invece può essere un vertice.
rdfs:label
  • Karmarkar's algorithm
  • Algorithme de Karmarkar
  • Algoritmo di Karmarkar
owl:sameAs
skos:subject
foaf:depiction
foaf:page
is dbpprop:redirect of