Algoritmo de Karmarkar

Considere um problema de programação linear na forma de matriz: O algoritmo de Karmarkar determina a próxima direção viável da e as escalas de volta por um fator de 0 < γ ≤ 1. Ele é descrito em um número de fontes. Como o atual algoritmo é bastante complicado, os pesquisadores foram à procura de uma versão mais intuitiva, e, em 1985, "inventaram" affine scaling, uma versão do algoritmo de Karmarkar que utiliza transformações afim, onde Karmarkar usava projetiva, apenas para perceber quatro anos mais tarde, que eles tinham reinventado um algoritmo publicado por um matemático Soviético I. I. Dikin em 1967. O método affine scaling pode ser descrito sucintamente da seguinte maneira. Note que o algoritmo affine scaling, enquanto aplicável a pequenos problemas de escala, não é um algoritmo de tempo polinomial. Karmarkar também ampliou o método para resolver problemas com restrições de número inteiro e problemas não convexos.

Isto é, existem 2 variáveis x 1 , x 2 {\displaystyle x_{1},x_{2}} e 11 restrições associadas a diferentes valores de p {\displaystyle p} . Esta figura mostra a cada iteração do algoritmo, (pontos vermelho). As restrições são mostradas como linhas azuis.

Na época em que ele inventou o algoritmo, Karmarkar foi contratado pela IBM como um postdoctoral fellow no IBM San Jose Research Laboratory, na Califórnia. Em 11 de agosto de 1983, ele deu um seminário na Universidade de Stanford, explicando o algoritmo, ainda afiliado à IBM. No Outono de 1983 Karmarkar, quando começou a trabalhar na AT&T e apresentou o seu artigo no 1984 ACM Symposium on Theory of Computing (STOC, realizada entre 30 de abril e 2 de Maio de 1984), declarando a AT&T Bell Laboratories como a sua filiação. Após a aplicação do algoritmo à otimização da rede telefônica da AT&T, eles perceberam que sua invenção poderia ser de importância prática. Em abril de 1985, a AT&T submeteu um pedido de patente para o algoritmo de Karmarkar. A patente tornou-se mais combustível para a atual controvérsia sobre a questão das patentes de software. Isso deixou muitos matemáticos inquietos, como Ronald Rivest (um dos titulares da patente do algoritmo RSA), que expressaram a opinião de que os algoritmos devem ser livres. Mesmo antes da patente ser concedida, foi alegado que pode ter havido técnica anterior que era aplicável. Matemáticos que se especializaram em análise numérica, incluindo Philip Gill e outros, alegaram que o algoritmo de Karmarkar é equivalente a um método de barreira de Newton com uma função de barreira logarítmica, se os parâmetros forem escolhidos adequadamente. O jurista Andrew Queixo opinou que o argumento Gill foi falho, visto que o método que eles descrevem não constituem um "algoritmo", pois requer escolhas de parâmetros que não seguem a lógica interna do método, mas dependem de orientação externa, essencialmente, a partir do algoritmo de Karmarkar. Além disso, as contribuições de Karmarkar são consideradas longe do óbvio, à luz de todos os trabalhos anteriores, incluindo Fiacco-McCormick, Gill e outros citados por Saltzman. A patente foi debatida no Senado dos EUA e concedida em reconhecimento à originalidade essencial do trabalho de Karmarkar, como Patente E.U.A. 4 744 028: "Métodos e aparelhos para alocação de recursos eficiente", em Maio de 1988.