Selmer Martin Johnson (21 May 1916 – 26 June 1996) was an American mathematician, a researcher at the
RAND Corporation
The RAND Corporation, doing business as RAND, is an American nonprofit global policy think tank, research institute, and public sector consulting firm. RAND engages in research and development (R&D) in several fields and industries. Since the ...
.
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 Twin Cities (historically known as University of Minnesota) is a public university, public Land-grant university, land-grant research university in the Minneapolis–Saint Paul, Twin Cities of Minneapolis and Saint ...
in 1938 and 1940 respectively.
World War II
World War II or the Second World War (1 September 1939 – 2 September 1945) was a World war, global conflict between two coalitions: the Allies of World War II, Allies and the Axis powers. World War II by country, Nearly all of the wo ...
interrupted Johnson's mathematical studies: he enlisted in the
United States Air Force
The United States Air Force (USAF) is the Air force, air service branch of the United States Department of Defense. It is one of the six United States Armed Forces and one of the eight uniformed services of the United States. Tracing its ori ...
, earning the rank of major. While serving, he also earned an M.S. in
meteorology
Meteorology is the scientific study of the Earth's atmosphere and short-term atmospheric phenomena (i.e. weather), with a focus on weather forecasting. It has applications in the military, aviation, energy production, transport, agricultur ...
from
New York University
New York University (NYU) is a private university, private research university in New York City, New York, United States. Chartered in 1831 by the New York State Legislature, NYU was founded in 1832 by Albert Gallatin as a Nondenominational ...
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
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, was supervised by David Bourgin, a student of
George David Birkhoff
George David Birkhoff (March21, 1884November12, 1944) was one of the top American mathematicians of his generation. He made valuable contributions to the theory of differential equations, dynamical systems, the four-color problem, the three-body ...
.
[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 and
D. R. Fulkerson, Johnson pioneered the use of
cutting-plane methods for
integer linear programming in solving the
travelling salesman problem
In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...
.
[.] 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.
s 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
*
Johnson bound
*
Johnson counter
* ()
*
Johnson's rule
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