Ellis L. Johnson

Johnson recibió el Premio de Teoría John von Neumann conjuntamente con Manfred W. Padberg en reconocimiento a sus contribuciones fundamentales a la programación entera y la optimización combinatoria . Su trabajo combina la teoría con el desarrollo de algoritmos, las pruebas computacionales y la solución de problemas complejos del mundo real, siguiendo la mejor tradición de la Investigación Operativa y las Ciencias de la Gestión. En su trabajo conjunto con Crowder y en trabajos posteriores con otros, demostraron cómo formular y resolver de manera eficiente programas 0-1 prácticos a gran escala con importantes aplicaciones en la industria y el transporte. ^{[ 5 ]}

El comité de selección citó entre las contribuciones de Johnson tres artículos importantes e influyentes que publicó a principios de los años setenta —dos de ellos junto con Ralph Gomory— , los cuales desarrollaron y ampliaron significativamente el enfoque de la teoría de grupos aplicado a la programación entera, iniciado por Gomory. En particular, Johnson demostró cómo este enfoque puede extenderse al caso de programas con enteros mixtos. Como resultado de este trabajo, Johnson contribuyó decisivamente al desarrollo de lo que se conoció como el enfoque subaditivo de la programación entera.

Todavía en la década de los setenta, en un artículo fundamental escrito en coautoría con Jack Edmonds , Johnson demostró cómo varios problemas básicos de optimización definidos en grafos pueden resolverse en tiempo polinomial reduciéndolos a problemas de emparejamiento ponderado. Un ejemplo es encontrar T-joins mínimos (es decir, conjuntos de aristas cuyos únicos extremos de grado impar son aquellos en un conjunto de vértices T especificado). Un caso especial importante es el problema aparentemente difícil de encontrar el recorrido más corto en un grafo que recorra cada arista al menos una vez, conocido como el problema del cartero. El marcado contraste entre la resolubilidad polinomial de este problema y la intratabilidad del problema del viajante, en el que se supone que el recorrido atraviesa vértices en lugar de aristas, ayudó a centrar la atención en el fenómeno tan típico de las estructuras combinatorias: dos problemas aparentemente muy similares resultan ser, en realidad, muy diferentes.