stringtranslate.com

Jack Edmonds

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 .

Carrera temprana

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.

Investigación

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]

Carrera

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.

Premios y honores

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]

Vida personal

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 .

Véase también

Referencias

  1. ^ "Antiguos_alumnos_tecnológicos_pp48".
  2. ^ "Galería del NIST de científicos, ingenieros y administradores distinguidos: se suman nueve retratos a la galería" (PDF) . 10 de octubre de 2014.
  3. ^ "El problema del viajante y P vs. NP: algunos trabajos teóricos de los años 1960 en el NIST sobre la complejidad de los algoritmos matemáticos".
  4. ^ Edmonds, Jack (10 de octubre de 2014). "El problema del viajante y P vs. NP: algunos trabajos teóricos de los años 1960 en el NIST sobre la complejidad de los algoritmos matemáticos" (PDF) .
  5. ^ "Jack Edmonds". Proyecto de genealogía matemática . Consultado el 23 de junio de 2022 .
  6. ^ Edmonds Jr., John Robert (1960). Una representación combinatoria para superficies poliédricas orientadas. hdl :1903/24820 . Consultado el 23 de junio de 2022 .
  7. ^ abc Edmonds, Jack (1991), "Un vistazo al cielo", en JK Lenstra; AHG Rinnooy Kan; A. Schrijver (eds.), Historia de la programación matemática: una colección de reminiscencias personales , CWI, Ámsterdam y Holanda Septentrional, Ámsterdam, págs. 32–54
  8. ^ Edmonds, Jack (1965). "Caminos, árboles y flores". Can. J. Math . 17 : 449–467. doi : 10.4153/CJM-1965-045-4 . S2CID  : 247198603.
  9. ^ Edmonds, Jack (1965). "Máxima correspondencia y un poliedro con 0,1 vértices". Revista de investigación de la Oficina Nacional de Normas, sección B. 69 ( 1 y 2): 125–130. doi : 10.6028/jres.069B.013 .
  10. ^ Meurant, Gerard (2014). Algoritmos y Complejidad . Elsevier. pag. pag. 4.ISBN 978-0-08093391-7Se 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]) .
  11. ^ Edmonds, Jack (1971). "Matroides y el algoritmo voraz". Matemáticas. Programación (Princeton Symposium Math. Prog. 1967) . 1 : 127–136.
  12. ^ ab Edmonds, Jack (1970). "Funciones submodulares, matroides y ciertos poliedros". En R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.). Estructuras combinatorias y sus aplicaciones (Proc. Conferencia de Calgary de 1969) . Gordon y Breach, Nueva York. págs. 69–87..
  13. ^ de Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni, eds. (2003), Optimización combinatoria: ¡Eureka, te encoges!, Apuntes de clase sobre informática, vol. 2570, Springer
  14. ^ Edmonds, Jack (1967). "Ramificaciones óptimas". Revista de investigación de la Oficina Nacional de Normas, sección B. 71B ( 4): 233–240. doi : 10.6028/jres.071B.032 .
  15. ^ Edmonds, Jack (1973), R. Rustin (ed.), "Ramificaciones disjuntas en los bordes", Combinatorial Algorithms | Courant Computer Science Symposium 9, 1972 , Monterey, California, 1972: Algorithmics Press, Nueva York: 91–96{{citation}}: Mantenimiento de CS1: ubicación ( enlace )
  16. ^ Edmonds, Jack; Giles, Richard (1977), PL Hammer; EL Johnson; BH Korte; GL Nemhauser (eds.), "Una relación min-max para funciones submodulares en gráficos", Estudios en programación entera | Actas del taller sobre programación entera, Bonn, 1975 , Annals of Discrete Mathematics, 1 , North-Holland, Ámsterdam: 185–204, doi :10.1016/S0167-5060(08)70734-9, ISBN 9780720407655
  17. Christoph Witzgall (2001), "Caminos, árboles y flores", Un siglo de excelencia en mediciones, estándares y tecnología (PDF) , Instituto Nacional de Estándares y Tecnología, pp. 140–144, archivado desde el original (PDF) el 25 de marzo de 2006 , consultado el 11 de agosto de 2011
  18. ^ UW Gazette, 7 de octubre de 1992: CAUT convocado para intervenir en el caso de Jack Edmonds
  19. ^ Introducción del editor Archivado el 27 de octubre de 2010 en Wayback Machine , en: Kenneth Westhues, ed., Workplace Mobbing in Academe: Reports from Twenty Universities, Lewiston: NY: The Edwin Mellen Press, 2004
  20. ^ Boletín diario de la Universidad de Waterloo, 5 de marzo de 2001: La conferencia rinde homenaje a Jack Edmonds
  21. ^ Fellows: Lista alfabética, Instituto de Investigación de Operaciones y Ciencias de la Gestión , archivado desde el original el 2019-05-10 , consultado el 2019-10-09

Enlaces externos