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

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

. 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 vast majority of the world's countries—including all of the great powers—forming two opposin ...

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

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

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

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

, 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 arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...

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

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

and

D. R. Fulkerson Delbert Ray Fulkerson (; August 14, 1924 – January 10, 1976) was an American mathematician who co-developed the FordFulkerson algorithm, one of the most well-known algorithms to solve the maximum flow problem in Flow network, networks. Early l ...

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

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

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

with the minimum known number of comparisons. Johnson graphs and the closely related

Johnson scheme In mathematics, the Johnson scheme, named after Selmer M. Johnson, is also known as the triangular association scheme. It consists of the set of all binary vectors ''X'' of length ''ℓ'' and weight ''n'', such that v=\left, X\=\binom.F. J. Mac ...

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

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