Algoritmo de Karmarkar

O algoritmo de Karmarkar é um algoritmo introduzido por Narendra Karmarkar, em 1984, para resolver problemas de programação linear. Foi o primeiro algoritmo razoavelmente eficiente para resolver esses problemas em tempo polinomial. O método elipsoide é também de tempo polinomial, mas provou ser ineficaz na prática.

Onde ${\displaystyle n}$ é o número de variáveis e ${\displaystyle L}$ é o número de bits de entrada, o algoritmo de Karmarkar requer ${\displaystyle O(n^{3.5}L)}$ operações, ${\displaystyle O(L)}$ números de dígitos, enquanto que no algoritmo elipsóide são necessárias ${\displaystyle O(n^{6}L)}$ operações. O tempo de execução do algoritmo de Karmarkar é:

${\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}$

usando FFT (Fast Fourier Transform).

O algoritmo de Karmarkar está na classe de método de pontos interiores: a atual estimativa para a solução não segue o limite da região viável como no método simplex, mas ele se move através do interior da região viável, melhorando a aproximação da ótima solução, por uma fração definitiva com cada iteração, e converge para uma ótima solução de dado racional.^[1]