Selmer Martin Johnson (21 de mayo de 1916 - 26 de junio de 1996) [1] fue un matemático estadounidense, investigador de la RAND Corporation .
Johnson nació el 21 de mayo de 1916 en Buhl, Minnesota . Obtuvo una licenciatura y luego una maestría en matemáticas de la Universidad de Minnesota en 1938 y 1940 respectivamente. La Segunda Guerra Mundial interrumpió los estudios matemáticos de Johnson: se alistó en la Fuerza Aérea de los Estados Unidos , obteniendo el grado de mayor. Mientras estaba en servicio, también obtuvo una maestría en meteorología de la Universidad de Nueva York en 1942. Después de la guerra, Johnson volvió a realizar estudios de posgrado en matemáticas en la Universidad de Illinois en Urbana-Champaign , y terminó su doctorado en 1950; su disertación, sobre el tema de la teoría de números , fue supervisada por David Bourgin, alumno de George David Birkhoff . [2] [3] [4] Ese mismo año, se unió a RAND Corporation, [4] convirtiéndose en parte de lo que se ha llamado "el grupo más notable de matemáticos que trabajan en optimización jamás reunido". [5] [6]
Con George Dantzig y DR Fulkerson , Johnson fue pionero en el uso de métodos de plano de corte para la programación lineal entera para resolver el problema del viajante . [5] [6] [7] También hizo importantes contribuciones a la teoría de la programación de procesos de producción , escribiendo uno de los primeros artículos sobre el problema de programación del taller de flujo que sentó las bases para muchas investigaciones futuras. [8]
Con LR Ford Jr. desarrolló el algoritmo de clasificación Ford-Johnson , que durante 20 años fue el tipo de comparación con el número mínimo conocido de comparaciones. [9]
Los gráficos de Johnson y el esquema de Johnson, estrechamente relacionado , llevan el nombre de Johnson, al igual que el algoritmo Steinhaus-Johnson-Trotter para generar todas las permutaciones de n elementos intercambiando elementos adyacentes.