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 The University of Minnesota, formally the University of Minnesota, Twin Cities, (UMN Twin Cities, the U of M, or Minnesota) is a public land-grant research university in the Twin Cities of Minneapolis and Saint Paul, Minnesota, United States. ...

in 1938 and 1940 respectively.

World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposing ...

interrupted Johnson's mathematical studies: he enlisted in the

United States Air Force The United States Air Force (USAF) is the Aerial warfare, air military branch, service branch of the United States Armed Forces, and is one of the eight uniformed services of the United States. Originally created on 1 August 1907, as a part ...

, earning the rank of major. While serving, he also earned an M.S. in

meteorology Meteorology is a branch of the atmospheric sciences (which include atmospheric chemistry and physics) with a major focus on weather forecasting. The study of meteorology dates back millennia, though significant progress in meteorology did no ...

from

New York University New York University (NYU) is a private research university in New York City. Chartered in 1831 by the New York State Legislature, NYU was founded by a group of New Yorkers led by then- Secretary of the Treasury Albert Gallatin. In 1832, th ...

in 1942. After the war, Johnson returned to graduate study in mathematics at the

University of Illinois at Urbana–Champaign The University of Illinois Urbana-Champaign (U of I, Illinois, University of Illinois, or UIUC) is a public land-grant research university in Illinois in the twin cities of Champaign and Urbana. It is the flagship institution of the Univer ...

, finishing his doctorate in 1950; his dissertation, on the subject of

number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...

, was supervised by David Bourgin, a student of

George David Birkhoff George David Birkhoff (March 21, 1884 – November 12, 1944) was an American mathematician best known for what is now called the ergodic theorem. Birkhoff was one of the most important leaders in American mathematics in his generation, and during ...

.Contributors, ''IRE Transactions on Information Theory'', April 1962, p. 261. This section may be seen attached to ; Johnson's paper, "A new upper bound for error-correcting codes", appears earlier in the same issue. In the same year, he joined the RAND Corporation, becoming part of what has been called "the most remarkable group of mathematicians working on optimization ever assembled"..

Research

With

George Dantzig George Bernard Dantzig (; November 8, 1914 – May 13, 2005) was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics. Dantzig is known for his ...

and D. R. Fulkerson, Johnson pioneered the use of

cutting-plane method In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed ''cuts''. Such procedures are commonly used ...

s for

integer linear program An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objectiv ...

ming in solving the

travelling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...

.. 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. Lester Randolph Ford Jr. (September 23, 1927 – February 26, 2017) was an American mathematician specializing in network flow problems. He was the son of mathematician Lester R. Ford Sr. Ford's paper with D. R. Fulkerson on the maximum flow p ...

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 The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of n elements. ...

for generating all permutations of ''n'' items by swapping adjacent elements.

References

{{DEFAULTSORT:Johnson, Selmer Martin 1916 births 1996 deaths 20th-century American mathematicians University of Minnesota College of Liberal Arts alumni New York University alumni University of Illinois Urbana-Champaign alumni RAND Corporation people People from St. Louis County, Minnesota

Biography

Research

See also

References