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 y obtuvo el rango 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 regresó a sus estudios de posgrado en matemáticas en la Universidad de Illinois en Urbana-Champaign , terminando su doctorado en 1950; su disertación, sobre el tema de la teoría de números , fue supervisada por David Bourgin, un estudiante deGeorge David Birkhoff . [2] [3] [4] En el mismo año, se unió a RAND Corporation, [4] pasando a formar 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 de comercio . [5] [6] [7] También hizo importantes contribuciones a la teoría de la programación de procesos de producción , escribiendo un artículo inicial sobre el problema de programación de flujo de trabajo 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.