Narendra Karmarkar

Narendra Krishna Karmarkar (nacido alrededor de 1956) es un matemático indio. Karmarkar desarrolló el algoritmo de Karmarkar. Está catalogado como un investigador altamente citado por el ISI.

Inventó uno de los primeros algoritmos de tiempo demostrablemente polinómico para programación lineal, que generalmente se conoce como método de punto interior. El algoritmo es una piedra angular en el campo de la programación lineal. Publicó su famoso resultado en 1984 mientras trabajaba para los Laboratorios Bell en Nueva Jersey.

Biografía

Karmarkar recibió su B.Tech en Ingeniería Eléctrica del IIT Bombay en 1978, su maestría del Instituto de Tecnología de California en 1979 y su doctorado en Ciencias de la Computación de la Universidad de California, Berkeley en 1983 bajo la supervisión de Richard M. Karp.. Karmarkar fue investigador postdoctoral en IBM Research (1983), miembro del personal técnico y miembro del Centro de Investigación de Ciencias Matemáticas, AT&T Bell Laboratories (1983-1998), profesor de matemáticas en el MIT. (1991), en el Instituto de Estudios Avanzados de Princeton (1996), y profesor de la Cátedra Homi Bhabha en el Instituto Tata de Investigación Fundamental de Mumbai de 1998 a 2005. Fue asesor científico del presidente del grupo TATA (2006-2007).). Durante este tiempo, Ratan Tata lo financió para ampliar la supercomputadora que había diseñado y creado como prototipo en TIFR. El modelo ampliado se situó por delante de la supercomputadora en Japón en ese momento y logró la mejor clasificación jamás alcanzada por la India en supercomputación. Fue director fundador de los laboratorios de investigación computacional en Pune, donde se realizó el trabajo de ampliación. Continúa trabajando en su nueva arquitectura para supercomputación.

Trabajo

Algoritmo de Karmarkar

El algoritmo de Karmarkar resuelve problemas de programación lineal en tiempo polinomial. Estos problemas están representados por una serie de restricciones lineales que involucran una serie de variables. El método anterior de resolución de estos problemas consistía en considerar el problema como un sólido de alta dimensión con vértices, donde la solución se abordaba atravesando de vértice a vértice. El novedoso método de Karmarkar aborda la solución cortando el sólido anterior en su recorrido. En consecuencia, los problemas complejos de optimización se resuelven mucho más rápido utilizando el algoritmo de Karmarkar. Un ejemplo práctico de esta eficiencia es la solución a un problema complejo de optimización de redes de comunicaciones, donde el tiempo de solución se redujo de semanas a días. Por tanto, su algoritmo permite tomar decisiones empresariales y políticas más rápidas. El algoritmo de Karmarkar ha estimulado el desarrollo de varios métodos de puntos interiores, algunos de los cuales se utilizan en implementaciones actuales de solucionadores de programas lineales.

Geometría de Galois

Después de trabajar en el método del punto interior, Karmarkar trabajó en una nueva arquitectura para supercomputación, basada en conceptos de geometría finita, especialmente geometría proyectiva sobre campos finitos.

Investigaciones actuales

Actualmente, está sintetizando estos conceptos con algunas ideas nuevas que llama esculpir el espacio libre (un análogo no lineal de lo que popularmente se ha descrito como doblar la esquina perfecta). Este enfoque le permite extender este trabajo al diseño físico de máquinas. Ahora está publicando actualizaciones sobre su trabajo reciente, incluido un resumen ampliado. Este nuevo paradigma se presentó en IVNC, Polonia, el 16 de julio de 2008, y en el MIT el 25 de julio de 2008. Algunos de sus trabajos recientes se publican en IEEE Xplore. Pronunció una conferencia sobre su trabajo en curso en IIT Bombay en septiembre de 2013. Dio una serie de conferencias de cuatro partes en FOCM 2014 (Fundamentos de Matemática Computacional) titulada "Hacia una visión más amplia de la teoría de la computación". La primera parte de esta serie de conferencias está disponible en el archivo de Cornell.

Premios

• La Asociación de Máquinas de Computación le otorgó el prestigioso Premio Paris Kanellakis en el año 2000 por su trabajo sobre métodos polinomio-tiempo interior para la programación lineal para "realizaciones teóricas específicas que han tenido un efecto significativo y demostrable en la práctica de la computación".
• Premio Centenario de Nacimiento Srinivasa Ramanujan para 1999, presentado por el Primer Ministro de la India.
• Distinguished Alumnus Award, Indian Institute of Technology, Bombay, 1996.
• Distinguished Alumnus Award, Computer Science and Engineering, University of California, Berkeley (1993).
• Premio Fulkerson en Matemáticas Discretas dado conjuntamente por la Sociedad Americana de Programación Matemáticas (1988)
• Fellow of Bell Laboratories (since 1987).
• Premio Fundadores de Instrumentos de Texas (1986).
• Marconi International Young Scientist Award (1985).
• Premio Golden Plate de la American Academy of Achievement, presentado por el ex presidente estadounidense (1985).
• Frederick W. Lanchester Prize of the Operations Research Society of America for the Best Published Contributions to Operations Research (1984).
• Presidente de la medalla de oro de la India, I.T. Bombay (1978).