Alan Jerome Hoffman (30 de mayo de 1924 - 18 de enero de 2021) fue un matemático estadounidense y miembro emérito de IBM , TJ Watson Research Center , IBM, en Yorktown Heights, Nueva York . Fue el editor fundador de la revista Linear Algebra and its Applications y poseía varias patentes. Contribuyó a la optimización combinatoria y a la teoría de valores propios de los grafos. Hoffman y Robert Singleton construyeron el grafo de Hoffman-Singleton , que es el único grafo de Moore de grado 7 y diámetro 2. [2]
Hoffman murió el 18 de enero de 2021, a la edad de 96 años. [3] [4]
Alan Hoffman nació y creció en la ciudad de Nueva York, residiendo primero en Bensonhurst , Brooklyn y luego en el Upper West Side de Manhattan, con su hermana Mildred y sus padres Muriel y Jesse. Alan supo desde muy temprana edad que quería una carrera en matemáticas. Fue un buen estudiante en todas las disciplinas, encontrando inspiración tanto en las artes liberales como en las ciencias. Pero estaba fascinado por el rigor del razonamiento deductivo que se encuentra en las matemáticas. Se graduó de la Escuela Secundaria George Washington en 1940 e ingresó en la Universidad de Columbia ese otoño, con una beca Pulitzer en 1940 a la edad de 16 años.
En Columbia, Hoffman se unió al Consejo de Debate, en parte para superar su miedo a hablar en público, y participó activamente en los movimientos para aumentar el apoyo estadounidense a los aliados en la creciente guerra contra el Eje, y en el movimiento para que Estados Unidos entrara directamente en la guerra. Aunque su trabajo académico consistía principalmente en matemáticas, incluidas clases pequeñas con eminencias en la materia, también estudió filosofía, literatura e historia de los gobiernos.
La Segunda Guerra Mundial interrumpió los estudios de Hoffman, pero no su interés por las matemáticas. Fue llamado a filas en febrero de 1943 y sirvió en el ejército de los Estados Unidos de 1943 a 1946, pasando un tiempo tanto en Europa como en el Pacífico. Hoffman se refiere elocuentemente a esos tres años como "el acontecimiento culminante de mi vida, con aventuras magnificadas por la sensibilidad de la juventud".
Durante su formación básica en la escuela de artillería antiaérea, consideró la posibilidad de desarrollar axiomas para la geometría de los círculos. Como no sabía dibujar, tenía en la cabeza una visión de las configuraciones del espacio (puntos, círculos y esferas) que representaban fenómenos análogos a la geometría de las líneas. Estas ideas se convertirían más tarde en la génesis de su tesis doctoral sobre los fundamentos de la geometría de inversión. La experiencia de desarrollar ideas en la mente en lugar de hacerlo en el papel o en la pizarra siguió siendo una práctica a lo largo de su carrera, una práctica que no recomendaba a otros, pero que le resultó muy útil a su mente única.
Después de un entrenamiento adicional en el ejército, Hoffman se convirtió en instructor en la escuela de metrología antiaérea [IL1] [2], enseñando trigonometría básica utilizada para rastrear globos y trazar deducciones de vientos en altura. Después de una formación adicional en ingeniería eléctrica en la Universidad de Maine y en los rudimentos de la telefonía de líneas largas, Hoffman fue asignado al 3186.º Batallón del Servicio de Señales y enviado al teatro europeo en diciembre de 1944, cuando la guerra allí se acercaba a su fin. Pasó un breve período en el teatro del Pacífico antes de regresar a casa en febrero de 1946. Durante su tiempo en el extranjero, él y otros enseñaron algo de matemáticas en pequeños cursos autoorganizados y registró sus incursiones en la geometría circular para compartirlas con el personal docente en Columbia.
Al regresar a Columbia en el otoño de 1946, Hoffman fue asignado para enseñar un curso de estudio matemático en la Facultad de Farmacia de Columbia. Consideró esto como una oportunidad para mejorar sus habilidades pedagógicas[3] y determinar si la carrera que planeaba en la docencia universitaria sería la opción más adecuada. Durante ese año académico, ganó confianza y habilidades en su enseñanza, cristalizó sus ideas sobre los axiomas de la geometría circular y le propuso matrimonio a Esther Walker, la hermana de un amigo del ejército. Hoffman comenzó sus estudios de posgrado en Columbia en el otoño de 1947, "rebosante de confianza".
Tras aprobar con éxito los exámenes y defender su tesis doctoral sobre los fundamentos de la geometría de inversión en 1950, Hoffman pasó un año posdoctoral en el Instituto de Estudios Avanzados de Princeton, patrocinado por la Oficina de Investigación Naval. Durante este año estableció un ritmo para su trabajo, basado en el mantra "Eres un matemático, haces matemáticas". [5]
Al final de su año posdoctoral, y sin haber conseguido un puesto académico en ningún lugar donde quisiera vivir, Hoffman se unió a la División de Matemáticas Aplicadas de la Oficina Nacional de Normas (NBS, ahora Instituto Nacional de Normas y Tecnología) en Washington DC. Esta elección, rechazada por amigos y colegas, fue fortuita. "Toda la trayectoria de mi carrera se basa en la experiencia de los cinco años que pasé en Washington en la NBS". Hoffman había sido contratado para ayudar a cumplir un contrato (Proyecto SCOOP) con la Oficina del Controlador Aéreo de la Fuerza Aérea de los Estados Unidos para seguir un programa de investigación y computación en un área de la que nunca había oído hablar: la programación lineal. Hoffman encontró que la nueva materia (tanto para él como para el mundo) era "una deliciosa combinación de desafío y diversión".
Hoffman aprendió programación lineal de George Dantzig, quien creía que su trabajo ayudaría a las organizaciones a operar de manera más eficiente mediante el uso de las matemáticas, un concepto que ahora, 70 años después, sigue siendo una realidad[IL4]. A través de este trabajo, Hoffman entró en contacto con conceptos empresariales de consultoría de gestión, fabricación y finanzas, áreas que disfrutaba, pero en las que nunca se sintió del todo cómodo. A través del Proyecto SCOOP, Hoffman conoció a otros investigadores de operaciones notables como Richard Bellman y Harold Kuhn. Aunque el código que escribió en 1951 "simplemente no funcionaba", una experiencia lo suficientemente desalentadora como para que nunca escribiera otro programa, Hoffman y sus coautores publicaron un artículo que demostraba, basándose en experimentos, que el método símplex era computacionalmente superior a sus competidores contemporáneos. Este artículo contenía los primeros experimentos computacionales con el método símplex y sirve como modelo para realizar experimentos computacionales en programación matemática.
Durante estos primeros años en la NBS, Hoffman desarrolló el primer ejemplo de ciclado en el método símplex, un ejemplo que aparece en numerosos libros de texto sobre el tema. Un breve artículo técnico de la NBS, aparentemente no muy difundido, mostraba que un punto que "casi" satisface un conjunto de desigualdades lineales está "cerca de": algún otro punto que sí lo hace, bajo cualquier definición razonable de "casi" y "cerca". Vale la pena considerar las implicaciones para los algoritmos de programación lineal que consideran restricciones "perezosas" o "suaves", o para los cuales los datos de restricción (coeficientes de la matriz y lado derecho) están sujetos a ruido.
Hoffman fue un organizador clave del influyente Segundo Simposio de Programación Lineal , celebrado en la Oficina en enero de 1955. El artículo de la NBS sobre el método símplex, ("Cómo resolver un problema de programación lineal ", Proc. Segundo Simposio de Programación Lineal, 1955) se distribuyó ampliamente a otros grupos que trabajaban en sus propios códigos para el algoritmo símplex. En 2020, este artículo es una mirada fascinante a los desafíos de resolver programas lineales en computadoras pequeñas (según los estándares actuales). El trabajo de Hoffman en la NBS incluyó intentos fallidos de usar la programación lineal para resolver un problema de subasta de adquisición combinatoria. Las subastas combinatorias siguen siendo un desafío hasta el día de hoy, debido a la abrumadora carga computacional asociada con el cálculo de soluciones óptimas [IL5]. El esfuerzo de la NBS utilizó un enfoque que se asemeja a la ramificación y el acotación, que ahora es el método estándar para resolver problemas de programación entera.
Junto con el matemático alemán Helmut Wielandt, Hoffman utilizó la programación lineal para estimar la distancia entre los valores propios de una matriz normal y los valores propios de otra matriz normal, en términos de la distancia entre las dos matrices. El resultado se basa en la observación de que toda matriz doblemente estocástica es la envoltura convexa de las matrices de permutación. Para la comunidad de investigación de operaciones, este resultado implica que, para la subclase de problemas de programación lineal que se denominan problemas de transporte, si los datos (lado derecho o valores de oferta y demanda) consisten en números enteros, entonces existe una solución óptima que solo toma valores enteros. El resultado general se conoce como el teorema de Hoffman-Wielandt y hay matemáticos que conocen a Hoffman solo a través de este resultado.
En la NBS, Hoffman exploró la conexión entre la dualidad de la programación lineal y otros problemas combinatorios. Esto condujo a una prueba simple pero elegante del teorema de König-Egerváry, que establece que para una matriz 0-1, el número máximo de 1 que aparecen en diferentes filas y columnas es igual al número mínimo de filas y columnas que, en combinación, incluyen todos los 1 de la matriz. Este trabajo temprano en la NBS y el interés continuo de Hoffman en utilizar igualdades lineales para demostrar teoremas combinatorios condujeron a colaboraciones con Harold Kuhn, David Gale y Al Tucker y al nacimiento de un subcampo que más tarde se conocería como combinatoria poliédrica. Hoffman influyó en la posterior incorporación de Jack Edmonds a la NBS (1959-1969), donde la materia floreció.
Mientras estaban en la NBS, Joe Kruskal y Hoffman demostraron que la unimodularidad total (el concepto, no el nombre) proporcionaba una explicación de por qué algunos programas lineales con datos enteros tienen soluciones enteras y otros no. También identificaron algunas condiciones suficientes para que una matriz tenga la propiedad requerida.
Hoffman también escribió sobre las condiciones de Lipschitz para sistemas de desigualdades lineales, límites de valores propios de matrices normales y las propiedades de patrones suaves de producción. En 1956, Hoffman dejó la Oficina y se mudó a Inglaterra con Esther y sus dos hijas pequeñas, Eleanor (que entonces tenía 2 años) y Elizabeth (que entonces tenía menos de 6 meses) para desempeñar el glamoroso papel de Oficial de Enlace Científico (matemáticas) en la sucursal londinense de la Oficina de Investigación Naval, con la misión de restablecer conexiones entre matemáticos estadounidenses y europeos. Este fue un año de escuchar y aprender, de establecer y renovar amistades y, por supuesto, de hacer matemáticas. Hizo matemáticas por toda Europa y descubrió en un tren a Frankfurt un hermoso teorema (pero con una prueba defectuosa, corregida más tarde por Jeff Kahn) que conectaba un tema de álgebra con su trabajo temprano sobre la geometría de los círculos. Otro artículo producido durante este período explora más a fondo las consecuencias de la unimodularidad total e introduce el concepto de circulación en un gráfico dirigido como una generalización del concepto de un flujo continuo, en el que dos de los nodos del gráfico juegan un papel especial.
Cuando el año en el extranjero se acercaba a su fin, Hoffman investigó dos puestos industriales en Nueva York: uno en un pequeño grupo de investigación matemática en el naciente IBM Research Lab en el norte del condado de Westchester y el otro enseñando y proporcionando apoyo general de investigación de operaciones para empleados de GE en la sede de la empresa en Manhattan. Hoffman eligió el puesto en la organización más grande y establecida debido a la ubicación, el salario y la oportunidad de ver si él y el campo de la investigación de operaciones podían tener éxito en los negocios. Hoffman encontró el trabajo fascinante y, en muchos aspectos, satisfactorio. La gerencia le permitió hacer matemáticas, siempre que no interfiriera con sus tareas asignadas. Hoffman continuó su investigación, la mayor parte de la cual era ortogonal a la misión del grupo de consultoría de gestión, en una elegante oficina en el corazón de Manhattan.
En el verano de 1960, Hoffman participó en un taller de verano sobre combinatoria organizado por el departamento de matemáticas de IBM Research. Quedó deslumbrado por el ambiente y por la "gente que lo rodeaba haciendo matemáticas". En 1961 aceptó la invitación de Herman Goldstine, Herb Greenberg y Ralph Gomory para unirse a IBM Research, pensando que sería un gran lugar para trabajar, pero que probablemente no duraría y que en pocos años conseguiría un "trabajo real" en el mundo académico. Aunque Hoffman trabajó como profesor visitante o adjunto en el Instituto Tecnológico Technion de Israel (que le otorgó un doctorado honorario), Yale, Stanford (donde pasó inviernos fríos durante casi una década), Rutgers, el Instituto Tecnológico de Georgia, la Universidad Yeshiva, la New School y la Universidad de la Ciudad de Nueva York y supervisó tesis doctorales en la Universidad de la Ciudad de Nueva York, Stanford, Yale y Princeton, siguió siendo miembro del Departamento de Matemáticas de IBM Research hasta su jubilación como IBM Fellow en 2002.
Al incorporarse a IBM, Hoffman era uno de los miembros más antiguos del departamento, que estaba compuesto principalmente por nuevos doctores. A pesar de haber obtenido su doctorado apenas 11 años antes, Hoffman asumió rápidamente el papel de mentor de estos jóvenes investigadores, conversando sobre su trabajo e intereses y brindándoles orientación. Trabajó brevemente como director del departamento y fue nombrado IBM Fellow en 1977. A lo largo de su carrera, publicó más de 200 artículos académicos, más de un tercio de ellos con coautores. Su alcance matemático abarcó numerosas áreas tanto en Álgebra como en Investigación de Operaciones. Fue coautor de artículos con muchos de sus colegas de IBM, colaborando eficazmente con todos, desde sus compañeros IBM Fellows hasta pasantes de verano y posdoctorados. El humor de Hoffman, su entusiasmo por las matemáticas, la música y los juegos de palabras, su amabilidad y generosidad fueron apreciados por todos los que lo conocieron.
Resumen de las contribuciones matemáticas (de sus notas en Documentos seleccionados de Alan Hoffman) [6]
El trabajo de Hoffman en geometría, que comenzó con su tesis "Sobre los fundamentos de la geometría de inversión", incluyó pruebas de propiedades de planos afines y el estudio de puntos de correlación de planos proyectivos finitos, condiciones sobre patrones de unión e intersección de conos (derivados en gran medida de su generalización de sus resultados anteriores sobre el rango de matrices reales). Produjo una prueba alternativa, basada en axiomas para ciertos sistemas abstractos de conjuntos convexos, de un resultado (de Scarf y otros) sobre el número de desigualdades necesarias para especificar una solución a un problema de programación entera. Un teorema sobre este sistema abstracto parece estar estrechamente relacionado con las antimatroides (también conocidas como geometrías convexas), aunque la conexión no se ha explorado por completo.
El trabajo de Hoffman en combinatoria amplió nuestra comprensión de varias clases de grafos. Una conferencia de 1956 de G. Hajós sobre grafos de intervalo condujo a la caracterización de Hoffman de los grafos de comparabilidad y, más tarde, a través de la colaboración con Paul Gilmore, al teorema GH (también atribuido a A. Ghouia-Houri). Motivado por el algoritmo de emparejamiento de Edmonds, Hoffman colaboró con Ray Fulkerson y M. McAndrew Hoffman para caracterizar conjuntos de números enteros que podrían corresponder a los grados y límites de cada par de vértices de aristas de dicho grafo. Además, consideraron qué grafos en la clase de todos los grafos que tienen un conjunto prescrito de grados y límites de aristas podrían transformarse mediante un conjunto específico de intercambios en cualquier otro conjunto de la clase. Las demostraciones se relacionan íntimamente con un concepto importante de la base de Hilbert. El artículo sobre cuadrados latinos autorrotogonales, con los coautores de IBM Don Coppersmith y R. Brayton, se inspiró en una solicitud para programar un torneo de dobles mixtos para evitar parejas en un club de raqueta local. Tiene la distinción de ser el único artículo que Hoffman discutiría fuera de la comunidad matemática.
Los conjuntos parcialmente ordenados fueron un tema de estudio frecuente para Hoffman. El artículo de 1977 con DE Schwartz utiliza la dualidad de programación lineal para generalizar la generalización de Green y Kleitman de 1976 del teorema de Dilworth sobre la descomposición de conjuntos parcialmente ordenados, en otro ejemplo más del papel unificador que desempeña la dualidad en muchos resultados combinatorios.
A lo largo de su carrera, Hoffman buscó pruebas alternativas, simples y elegantes, a los teoremas establecidos. Estas pruebas alternativas a menudo dieron lugar a generalizaciones y extensiones. A fines de la década de 1990, colaboró con Cao, Chvátal y Vince para desarrollar una prueba alternativa, utilizando métodos elementales en lugar del álgebra lineal o el teorema de Ryser sobre matrices cuadradas 0-1.
El trabajo de Hoffman sobre desigualdades matriciales y valores propios es un elemento básico en cualquier curso sobre teoría de matrices. De particular encanto, y en consonancia con su afición por los enfoques unificadores, es su artículo de 1975 sobre funciones G lineales. Si bien la prueba de la variación de Gerschgorin especificada es más larga y más compleja que otras, cubre todas las variaciones de Ostrowski y muchas variaciones adicionales como casos especiales.
Hoffman era un anciano alentador, pero no participó activamente en el desarrollo de una serie de productos de programación lineal y entera de IBM. Sin embargo, continuó investigando sobre los aspectos combinatorios y algebraicos de la programación lineal y las desigualdades lineales, incluida una deliciosa abstracción de la dualidad de la programación lineal (1963). También continuó utilizando las propiedades de las desigualdades lineales para demostrar (o volver a demostrar, de manera más elegante) resultados en convexidad.
Una colaboración con Shmuel Winograd, también miembro de IBM en el departamento de Matemáticas, produjo un algoritmo eficiente para encontrar todas las distancias más cortas en una red dirigida, utilizando pseudo-multiplicación de matrices. Una serie de artículos sobre poliedros reticulares (algunos con Don Schwarts) introdujeron el concepto de poliedros reticulares, lo que dio lugar a otro ejemplo de dualidad combinatoria.
Tras una colaboración con Ray Fulkerson y Rosa Oppenheim sobre matrices balanceadas, Hoffman generalizó el resultado de Ford-Fulkerson Max Flow – Min Cut a otros casos (flujo en nodos, arcos no dirigidos, etc.) proporcionando una prueba de que todos los casos conocidos anteriormente eran casos especiales. Este artículo también introdujo el concepto de (pero de nuevo, no el nombre) de integralidad dual total, una idea detrás de la mayoría de los usos de la programación lineal para demostrar teoremas combinatorios extremales.
A lo largo de su carrera, Hoffman estudió la clase de problemas de programación entera que se podían resolver maximizando sucesivamente las variables en algún orden. Uno de esos casos es el problema de transporte completo, en el caso en que el coeficiente de costo exhibe una propiedad particular descubierta más de un siglo antes por el matemático francés Gaspard Monge. Este enfoque, llamado simplemente "simple" en el artículo de Hoffman, fue posteriormente considerado "codicioso" por Edmonds y Fulkerson. La propiedad de Monge da lugar a un antimatroide y, mediante el uso de ese antimatroide, el resultado de Hoffman se extiende fácilmente al caso de problemas de transporte incompletos. Hoffman reutilizó el término "codicioso" para describir una subclase de matrices 0-1 para las que el programa lineal dual se puede resolver mediante el algoritmo codicioso para todos los lados derechos y todas las funciones objetivo con coeficientes decrecientes (en el índice de la variable). Junto con Kolen y Sakarovitch, demostró que para estas matrices, el programa entero correspondiente tiene una solución entera óptima para datos enteros. El elegante y breve artículo de 1992 proporciona una caracterización de matrices 0-1 para las que se pueden resolver problemas de empaquetamiento y cubrimiento mediante un enfoque voraz. Proporciona una unificación de resultados para problemas de ruta más corta y de árbol de expansión mínimo. Su artículo final sobre este tema "On greedy algorithms, partial ordered sets and submodular functions", coescrito con Dietrich, apareció en 2003.
Hoffman visitó y revisó el tema de los espectros de gráficos, abordando la singularidad del esquema de asociación triangular en un artículo de 1959, los gráficos de Moore con diámetros 2 y 3 en 1960 (con R Singleton), el polinomio de un gráfico en 1963, el gráfico lineal de un diseño de bloque incompleto equilibrado simétrico (con Ray-Chaudhuri) en 1965, las conexiones entre los valores propios y las coloraciones de un gráfico (en 1970), las conexiones entre los valores propios y las particiones de los bordes en un gráfico en 1972, y muchos más, incluida la exploración de las propiedades de la matriz de incidencia de bordes versus trayectorias de gráficos paralelos en serie (relacionados con empaquetamientos voraces) con Schieber en 2002.
Hoffman fue elegido miembro de la Academia Nacional de Ciencias en 1982, de la Academia Estadounidense de Artes y Ciencias en 1987 y de la clase inaugural de INFORMS Fellows en 2002. A lo largo de su larga carrera, Hoffman formó parte del consejo editorial de once revistas y fue editor fundador de Linear Algebra and its Applications. En 1992, junto con Phillip Wolfe (también de IBM), recibió el Premio de Teoría John von Neumann de ORSA y TIMS[6], predecesores de INFORMS[7]. Al presentar el premio, George Nemhauser reconoció a Hoffman y Wolfe como los líderes intelectuales del grupo de programación matemática de IBM. Citó a Hoffman por su trabajo en combinatoria y programación lineal y por su trabajo temprano sobre la eficiencia computacional del método símplex durante su tiempo en NBS. En agosto de 2000, Hoffman fue honrado por la Sociedad de Programación Matemática como uno de los 10 destinatarios (3 de IBM) del Premio Fundadores.
En una biografía publicada en un número de Linear Algebra and its Applications dedicado a Hoffman con motivo de su sexagésimo quinto cumpleaños, Uriel Rothblum escribió que "más allá de sus contribuciones académicas y profesionales, Hoffman tiene una capacidad incomparable para disfrutar de todo lo que hace. Disfruta de cantar, el ping pong, los juegos de palabras, las historias ingeniosas y, posiblemente tanto como cualquier otra cosa, de hacer matemáticas".
Esther Hoffman murió de una enfermedad de la sangre en el verano de 1988. Alan se casó con Elinor Hershaft, diseñadora de interiores, en 1990. Se divorciaron en 2014. Elinor murió en octubre de 2020. Hoffman pasó sus últimos años en la comunidad de jubilados The Osborn en Rye, Nueva York. Le sobreviven sus hijas, Eleanor y Elizabeth.
Alan Hoffman recibió numerosos premios. [7]
{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)