Selmer M. Johnson
Encyclopedia
Selmer Martin Johnson was an American mathematician, a researcher at the RAND Corporation.
. 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 a 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
. 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."
and D. R. Fulkerson
, Johnson pioneered the use of cutting-plane method
s for integer linear programming in solving the travelling salesman problem
. 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.
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.
Biography
Johnson was born on May 21, 1916 in Buhl, MinnesotaBuhl, Minnesota
Buhl is a city in Saint Louis County, Minnesota, United States. The population was 1,000 at the 2010 census.U.S. Highway 169 serves as a main arterial route in the community.Buhl's motto is "The Finest Water in America ".-Geography:...
. He earned a B.A. and then an M.A. in mathematics from the University of Minnesota
University of Minnesota
The University of Minnesota, Twin Cities is a public research university located in Minneapolis and St. Paul, Minnesota, United States. It is the oldest and largest part of the University of Minnesota system and has the fourth-largest main campus student body in the United States, with 52,557...
in 1938 and 1940 respectively. World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
interrupted Johnson's mathematical studies: he enlisted in the United States Air Force
United States Air Force
The United States Air Force is the aerial warfare service branch of the United States Armed Forces and one of the American uniformed services. Initially part of the United States Army, the USAF was formed as a separate branch of the military on September 18, 1947 under the National Security Act of...
, earning the rank of a major. While serving, he also earned an M.S. in meteorology
Meteorology
Meteorology is the interdisciplinary scientific study of the atmosphere. Studies in the field stretch back millennia, though significant progress in meteorology did not occur until the 18th century. The 19th century saw breakthroughs occur after observing networks developed across several countries...
from New York University
New York University
New York University is a private, nonsectarian research university based in New York City. NYU's main campus is situated in the Greenwich Village section of Manhattan...
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
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, was supervised by David Bourgin, a student of George David Birkhoff
George David Birkhoff
-External links:* − from National Academies Press, by Oswald Veblen....
. 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 DantzigGeorge Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....
and D. R. Fulkerson
D. R. Fulkerson
Delbert Ray Fulkerson was a mathematician who co-developed the Ford-Fulkerson algorithm, one of the most well-known algorithms to solve the maximum flow problem in networks....
, Johnson pioneered the use of cutting-plane method
Cutting-plane method
In mathematical optimization, the cutting-plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts...
s for integer linear programming in solving the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
. He also made important contributions to the theory of scheduling production processes
Scheduling (production processes)
Scheduling is an important tool for manufacturing and engineering, where it can have a major impact on the productivity of a process. In manufacturing, the purpose of scheduling is to minimize the production time and costs, by telling a production facility when to make, with which staff, and on...
, writing an early paper on the Flow Shop Scheduling Problem
Flow Shop Scheduling Problem
Flow Shop Scheduling Problems, or FSPs, are a class of scheduling problems with a work shop or group shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources 1,2,...,m in compliance with given processing orders...
that set the stage for much future research.
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.