Selmer M. Johnson

Selmer Martin Johnson (21 May 1916 – 26 June 1996) was an American mathematician, a researcher at the RAND Corporation.

Biography Johnson was born on May 21, 1916, in Buhl, Minnesota. He earned a B.A. and then an M.A. in mathematics from the University of Minnesota in 1938 and 1940 respectively. World War II interrupted Johnson's mathematical studies: he enlisted in the United States Air Force, earning the rank of major. While serving, he also earned an M.S. in meteorology from New York University in 1942. After the war, Johnson returned to graduate study in mathematics at the University of Illinois at Urbana–Champaign, finishing his doctorate in 1950; his dissertation, on the subject of number theory, was supervised by David Bourgin, a student of George David Birkhoff. In the same year, he joined the RAND Corporation,

Research With George Dantzig and D. R. Fulkerson, Johnson pioneered the use of cutting-plane methods for integer linear programming in solving the travelling salesman problem. He also made important contributions to the theory of scheduling production processes, writing an early paper on the flow shop scheduling problem that set the stage for much future research.

With L. R. Ford Jr. he developed the Ford–Johnson algorithm for sorting, which for 20 years was the comparison sort with the minimum known number of comparisons.

Johnson graphs and the closely related Johnson scheme are named after Johnson, as is the Steinhaus–Johnson–Trotter algorithm for generating all permutations of n items by swapping adjacent elements.