Selmer Martin Johnson (21 May 1916 – 26 June 1996)[1] 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.[2][3][4] In the same year, he joined the RAND Corporation,[4] becoming part of what has been called "the most remarkable group of mathematicians working on optimization ever assembled".[5][6]

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.[5][6][7] 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.[8]

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.[9]

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.

See also

References

  1. ^ "FamilySearch.org". FamilySearch. Retrieved 17 July 2023.
  2. ^ Selmer Martin Johnson at the Mathematics Genealogy Project
  3. ^ Commencement program, Univ. of Illinois, 1950, retrieved September 29, 2011.
  4. ^ a b Contributors, IRE Transactions on Information Theory, April 1962, p. 261. This section may be seen attached to doi:10.1109/TIT.1962.1057713; Johnson's paper, "A new upper bound for error-correcting codes", appears earlier in the same issue.
  5. ^ a b Chvátal, Vašek; Cook, William (2009), "The birth of the cutting-plane method", 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, Springer, pp. 7–9, ISBN 978-3-540-68274-5.
  6. ^ a b Grötschel, M.; Nemhauser, G. L. (2008), "George Dantzig's contributions to integer programming", Discrete Optimization, 5 (2): 168–173, doi:10.1016/j.disopt.2007.08.003.
  7. ^ Gass, Saul I.; Assad, Arjang (2005), An annotated timeline of operations research: an informal history, International series in operations research & management science, vol. 75, Springer, p. 95, ISBN 978-1-4020-8112-5.
  8. ^ Herrmann, Jeffrey W. (2010), "The Perspectives of Taylor, Gantt, and Johnson: How to Improve Production Scheduling" (PDF), International Journal of Operations and Quantitative Management, 16 (3): 243–254.
  9. ^ Mahmoud, Hosam M. (2011), "12.3.1 The Ford–Johnson algorithm", Sorting: A Distribution Theory, Wiley Series in Discrete Mathematics and Optimization, vol. 54, John Wiley & Sons, pp. 286–288, ISBN 9781118031131
Categories