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 que resolve esses problemas em tempo polinomial. O é também de tempo polinomial, mas provou ser ineficaz na prática. Onde é o número de variáveis e é o número de bits de entrada, o algoritmo de Karmarkar requer operações, números de dígitos, enquanto que no algoritmo elipsóide são necessárias operações. O tempo de execução do algoritmo de Karmarkar é: 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.