Селмер Мартин Джонсон (21 мая 1916 — 26 июня 1996) [1] — американский математик, научный сотрудник RAND Corporation .
Джонсон родился 21 мая 1916 года в Буле, штат Миннесота . Он получил степень бакалавра, а затем степень магистра математики в Университете Миннесоты в 1938 и 1940 годах соответственно. Вторая мировая война прервала математические занятия Джонсона: он поступил на службу в ВВС США , получив звание майора. Во время службы он также получил степень магистра метеорологии в Нью-Йоркском университете в 1942 году. После войны Джонсон вернулся в аспирантуру по математике в Иллинойсский университет в Урбане-Шампейне , получив докторскую степень в 1950 году; его диссертация по теории чисел была написана под руководством Дэвида Бургина, студентаДжордж Дэвид Биркхофф . [2] [3] [4] В том же году он присоединился к RAND Corporation, [4] став частью того, что было названо «самой замечательной группой математиков, работающих над оптимизацией, когда-либо собиравшейся». [5] [6]
Вместе с Джорджем Данцигом и Д. Р. Фулкерсоном Джонсон впервые применил методы секущей плоскости для целочисленного линейного программирования при решении задачи коммивояжера . [5] [6] [7] Он также внес важный вклад в теорию планирования производственных процессов , написав раннюю статью о проблеме планирования производственного процесса, которая заложила основу для многих будущих исследований. [8]
Вместе с Л.Р. Фордом-младшим он разработал алгоритм сортировки Форда-Джонсона , который в течение 20 лет был сортировкой сравнением с минимально известным числом сравнений. [9]
Графы Джонсона и тесно связанная с ним схема Джонсона названы в честь Джонсона, как и алгоритм Штейнхауса-Джонсона-Троттера для генерации всех перестановок из n элементов путем замены соседних элементов местами.