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

RAND Corporation The RAND Corporation (from the phrase "research and development") is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is financ ...

Biography

Johnson was born on May 21, 1916, in

Buhl, Minnesota Buhl is a city in Saint Louis County, Minnesota, United States. Its population was 1,000 at the 2010 census. U.S. Highway 169 serves as a main route in the community. The city's motto is "The Finest Water in America". History A post office ca ...

. 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 university, public Land-grant university, land-grant research university in the Minneapolis–Saint Paul, Tw ...

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 World War II by country, vast majority of the world's countries—including all of the great power ...

interrupted Johnson's mathematical studies: he enlisted in the

United States Air Force The United States Air Force (USAF) is the air 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 of the United States Army S ...

, 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, ...

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 Unive ...

, 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, "Math ...

, 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 duri ...

.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 de ...

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 objective ...

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 Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of vary ...

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 In computer science, merge-insertion sort or the Ford–Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson. It uses fewer comparisons in the worst case than the best previously known algor ...

for sorting, which for 20 years was the

comparison sort A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should oc ...

with the minimum known number of comparisons.

Johnson graph Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph J(n,k) are the k-element subsets of an n-element set; two vertices are adjacent when the intersection of the two vertices (subse ...

s 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. Ea ...

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