Ellis L. Johnson
# Ellis L. Johnson

Ellis Lane Johnson (* 26. Juli 1938 in Athens (Georgia)) ist ein US-amerikanischer Informatiker und Angewandter Mathematiker (Operations Research).

## Ausbildung und Karriere

Johnson wuchs auf einer Farm auf (und auch später legte er sich eine Farm bei Madison (Georgia) zu). Er studierte am Georgia Institute of Technology mit dem Bachelorabschluss 1960 und an der University of California, Berkeley, wo er 1962 seinen Masterabschluss machte und 1965 bei George B. Dantzig promoviert wurde (Network Flows, Graphs and Integer Programming).
Von 1964 bis 1968 war er Assistant Professor für Betriebswirtschaft an der Yale University. Nach einem Sabbatical Aufenthalt an der ETH Zürich wollte er wieder in die Forschung. Ab 1968 war er am Thomas J. Watson Research Center von IBM, an dem er bis 1993 blieb. Die Ernennung zum IBM Fellow 1990 erlaubte ihm fünf Jahre Forschung nach freier Wahl. Er ging an das Georgia Institute of Technology, wo er mit George Nemhauser ein Zentrum für Optimierung aufbaute. 1995 verließ er IBM und wurde Mitglied der Fakultät auf einem von Coca-Cola gesponserten Lehrstuhl in der H. Milton Stewart School of Industrial and Systems Engineering. Er unterrichtet im Rahmen seiner Professur an der Georgia Tech auch in Shanghai.
1972 bis 1978 war daneben Adjunct Professor an der University of Waterloo. 1980 erhielt er einen US Senior Scientist Award der Humboldt-Stiftung und war mit dieser Förderung 1980/81 an der Universität Bonn. 1990 wurde er IBM Fellow. Er ist Mitglied der National Academy of Engineering.

## Forschung

Er ist bekannt für Beiträge zur Ganzzahligen Programmierung, wobei er in den 1970er Jahren mit Ralph E. Gomory zusammenarbeitete. Mit Jack Edmonds löste er das Briefträgerproblem (Chinese Postman Problem) mit Matching-Methoden. Sie zeigten, dass es in polynomialer Zeit lösbar ist (im Gegensatz zu dem scheinbar ähnlichen, aber weit schwierigeren Problem des Handlungsreisenden).

## Preise und Ehrungen

* 1980: US Senior Scientist Award der Humboldt-Stiftung
* 1983: Frederick-W.-Lanchester-Preis
* 1985: Dantzig-Preis
* 2000: John-von-Neumann-Theorie-Preis