Jack R. Edmonds (nacido el 5 de abril de 1934) es un informático y matemático nacido y educado en Estados Unidos que vivió y trabajó en Canadá durante gran parte de su vida. Ha realizado contribuciones fundamentales en los campos de la optimización combinatoria , la combinatoria poliédrica , las matemáticas discretas y la teoría de la computación. Recibió el Premio de Teoría John von Neumann en 1985 .
Edmonds asistió a la McKinley Technology High School , graduándose en 1952; [1] y ha hablado sobre la influencia que esta escuela tuvo en su carrera (por ejemplo, en su inducción a la Galería NIST de 2014 [2] [3] [4] ). Edmonds asistió a la Universidad de Duke antes de completar su licenciatura en la Universidad George Washington en 1957. Posteriormente recibió una maestría en 1960 en la Universidad de Maryland con Bruce L. Reinhart con una tesis sobre el problema de incrustar gráficos en superficies. [5] [6] De 1959 a 1969 trabajó en el Instituto Nacional de Estándares y Tecnología (entonces la Oficina Nacional de Estándares), y fue miembro fundador de la recién creada Sección de Investigación de Operaciones de Alan Goldman en 1961. Goldman demostró ser una influencia crucial al permitirle a Edmonds trabajar en un taller patrocinado por RAND Corporation en Santa Mónica, California. Fue allí donde Edmonds presentó por primera vez sus hallazgos sobre la definición de una clase de algoritmos que pudieran ejecutarse de manera más eficiente. La mayoría de los estudiosos de la combinatoria, durante esta época, no se centraban en los algoritmos. Sin embargo, Edmonds se sintió atraído por ellos y estas investigaciones iniciales fueron desarrollos clave para su trabajo posterior entre matroides y optimización. Pasó los años de 1961 a 1965 en el tema de NP versus P y en 1966 originó las conjeturas NP ≠ P y NP ∩ coNP = P.
El artículo de Edmonds de 1965 “Paths, Trees and Flowers” fue un artículo preeminente en el que inicialmente se sugirió la posibilidad de establecer una teoría matemática de algoritmos combinatorios eficientes. Una de sus primeras y notables contribuciones es el algoritmo Blossom para construir emparejamientos máximos en grafos, descubierto en 1961 [7] y publicado en 1965. [8] Este fue el primer algoritmo de tiempo polinomial para el emparejamiento máximo en grafos. Su generalización a grafos ponderados [9] fue un avance conceptual en el uso de ideas de programación lineal en la optimización combinatoria . Selló la importancia de que haya pruebas, o "testigos", de que la respuesta para una instancia es sí y de que haya pruebas, o "testigos", de que la respuesta para una instancia es no. En este artículo sobre el algoritmo Blossom, Edmonds también caracteriza los problemas factibles como aquellos que se pueden resolver en tiempo polinomial; este es uno de los orígenes de la tesis de Cobham-Edmonds . [10]
Un avance de la tesis de Cobham-Edmonds fue la definición del concepto de tiempo polinómico, que caracteriza la diferencia entre un algoritmo práctico y uno impráctico (en términos modernos, un problema tratable o un problema intratable). Hoy en día, los problemas que se pueden resolver en tiempo polinómico se denominan clase de complejidad PTIME o simplemente P.
El artículo de Edmonds “Maximum Matching and a Polyhedron with 0-1 Vertices” junto con su trabajo anterior proporcionaron sorprendentes algoritmos de tiempo polinomial para la construcción de emparejamientos máximos. En particular, estos artículos demostraron cómo una buena caracterización del poliedro asociado con un problema de optimización combinatoria podría conducir, a través de la teoría de dualidad de la programación lineal, a la construcción de un algoritmo eficiente para la solución de ese problema.
Otro trabajo destacado de Edmonds es en el área de los matroides . Encontró una descripción poliédrica para todos los árboles de expansión de un grafo y, de manera más general, para todos los conjuntos independientes de un matroide. [11] Sobre la base de esto, como una aplicación novedosa de la programación lineal a las matemáticas discretas, demostró el teorema de intersección de matroides , un teorema combinatorio mínimo-máximo muy general [12] [13] que, en términos modernos, mostró que el problema de intersección de matroides se encontraba tanto en NP como en co-NP . Edmonds es bien conocido por sus teoremas sobre algoritmos de ramificación de peso máximo [14] y ramificaciones disjuntas de aristas de empaquetamiento [15] y su trabajo con Richard Karp en algoritmos de flujo más rápido . El teorema de descomposición de Edmonds-Gallai describe grafos finitos desde el punto de vista de los emparejamientos. Introdujo los polimatroides , [12] los flujos submodulares con Richard Giles, [16] y los términos desorden y bloqueador en el estudio de los hipergrafos . [7] Un tema recurrente en su trabajo [17] es buscar algoritmos cuya complejidad temporal esté limitada polinomialmente por su tamaño de entrada y complejidad de bits. [7]
A partir de 1969, con excepción de 1991-1993, ocupó un puesto docente en el Departamento de Combinatoria y Optimización de la Facultad de Matemáticas de la Universidad de Waterloo , donde su investigación abarcó problemas de optimización combinatoria y poliedros asociados. Durante este tiempo supervisó el trabajo de doctorado de una docena de estudiantes. Dictó cursos o realizó estancias de investigación en la Universidad de Duke, la Universidad George Washington, la Universidad de Maryland, Stanford, Princeton, Cornell, así como en universidades de China, Lovaina (Bélgica), Copenhague, Dinamarca Meridional (Odense), París, Marsella, Grenoble (Francia), así como Bonn y Colonia (Alemania).
Entre 1991 y 1993, estuvo involucrado en una disputa ("el asunto Edmonds") con la Universidad de Waterloo, [18] [19] en la que la universidad afirmó que una carta presentada constituía una carta de renuncia, lo que Edmonds negó. [20] El conflicto se resolvió en 1993 y regresó a la universidad.
Edmonds se retiró de la Universidad de Waterloo en 1999.
Edmonds recibió en 1985 el Premio de Teoría John von Neumann .
En 2001, su artículo "Caminos, árboles y flores" fue reconocido como una publicación destacada por el Instituto Nacional de Estándares y Tecnología en su edición de celebración de Un siglo de excelencia en mediciones Estándares y tecnología
Fue elegido miembro de la clase de 2002 de miembros del Instituto de Investigación de Operaciones y Ciencias de la Gestión . [21]
En 2006, la Reina de Dinamarca le entregó a Edmonds un Doctorado Honoris Causa de la Universidad del Sur de Dinamarca .
En 2014 fue distinguido como Científico Distinguido e incluido en la Galería del Instituto Nacional de Estándares y Tecnología.
El quinto Taller Aussois sobre Optimización Combinatoria en 2001 estuvo dedicado a él. [13]
El hijo de Jack, Jeff Edmonds, es profesor de informática en la Universidad de York , y su esposa, Kathie Cameron, es profesora de matemáticas en la Universidad Laurier .
Se dice que un problema es
factible
si se puede resolver en tiempo polinomial (como se afirma por primera vez en Edmonds [26] [1965, Paths, trees, and flowers]).
{{citation}}: Mantenimiento de CS1: ubicación ( enlace )