Jack R. Edmonds (nacido el 5 de abril de 1934) es un informático y matemático educado y nacido 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 , la matemática discreta y la teoría de la computación. Recibió el Premio de Teoría John von Neumann en 1985 .
Edmonds asistió a McKinley Technology High School y se graduó en 1952; [1] y ha hablado sobre la influencia que esta escuela tuvo en su carrera (por ejemplo, en su incorporación a la Galería NIST en 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 aquí donde Edmonds presentó por primera vez sus hallazgos sobre la definición de una clase de algoritmos que podrían ejecutarse de manera más eficiente. La mayoría de los estudiosos de la combinatoria, durante este tiempo, 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. Dedicó los años de 1961 a 1965 al 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 destacado al sugerir inicialmente 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 coincidencias máximas en gráficos, descubierto en 1961 [7] y publicado en 1965. [8] Este fue el primer algoritmo de tiempo polinómico para la coincidencia máxima en gráficos. Su generalización a gráficos ponderados [9] fue un avance conceptual en el uso de ideas de programación lineal en optimización combinatoria . Selló la importancia de que haya pruebas, o "testigos", de que la respuesta para un caso es sí y que haya pruebas, o "testigos", de que la respuesta para un caso es no. En este artículo sobre algoritmos en flor, 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 gran avance de la tesis de Cobham-Edmonds fue definir el concepto de tiempo polinomial que caracteriza la diferencia entre un algoritmo práctico y uno poco práctico (en términos modernos, un problema tratable o un problema intratable). Hoy en día, los problemas que se pueden resolver en tiempo polinomial 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, proporcionó sorprendentes algoritmos de tiempo polinómico para la construcción de coincidencias máximas. 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 la dualidad de la programación lineal, a la construcción de un algoritmo eficiente para la solución de ese problema.
Otro trabajo emblemático de Edmonds se encuentra en el área de las matroides . Encontró una descripción poliédrica para todos los árboles generadores de un gráfico y, de manera más general, para todos los conjuntos independientes de una matroide. [11] Partiendo de esto, como una aplicación novedosa de la programación lineal a las matemáticas discretas, demostró el teorema de intersección matroide , un teorema combinatorio mínimo-máximo muy general [12] [13] que, en términos modernos, demostró que la intersección matroide El problema residía 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 de borde disjunto [15] y su trabajo con Richard Karp sobre algoritmos de flujo más rápido . El teorema de descomposición de Edmonds-Gallai describe gráficos finitos desde el punto de vista de las coincidencias. Introdujo los polimatroides , [12] los flujos submodulares con Richard Giles, [16] y los términos desorden y bloqueador en el estudio de los hipergráficos . [7] Un tema recurrente en su trabajo [17] es buscar algoritmos cuya complejidad temporal esté polinomialmente limitada por su tamaño de entrada y complejidad de bits. [7]
A partir de 1969, con la 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. Supervisó el trabajo doctoral de una docena de estudiantes en este tiempo. Impartió 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 del Sur (Odense), París, Marsella, Grenoble (Francia), así como Bonn y Colonia (Alemania).
De 1991 a 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 "Paths, Trees and Flowers" fue honrado como 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 estándares y tecnología de mediciones.
Fue elegido miembro de la promoción de 2002 de becarios del Instituto de Investigación de Operaciones y Ciencias de la Gestión . [21]
En 2006, la Reina de Dinamarca otorgó a Edmonds un Doctorado Honoris Causa de la Universidad del Sur de Dinamarca .
En 2014 fue honrado como Científico Distinguido y admitido en la Galería del Instituto Nacional de Estándares y Tecnología.
A él se le dedicó el quinto Taller Aussois sobre Optimización Combinatoria en 2001. [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 puede resolverse en tiempo polinomial (como se afirmó por primera vez en Edmonds [26] [1965, Paths, Trees, and Flowers]).
{{citation}}: Mantenimiento CS1: ubicación ( enlace )