David Stifler Johnson
David Stifler Johnson (born December 9, 1945 in Washington, DC - † March 8, 2016 ) was an American computer scientist .
Education and career
Johnson studied mathematics at Amherst College (Bachelor 1967 summa cum laude ) and at the Massachusetts Institute of Technology , where he received his master's degree from Seymour Papert in 1968 ( Look ahead strategies in one person games with randomly generated game trees ) and in 1973 from Michael J. Fisher (MIT) received his PhD ( Near optimal bin-packing algorithms ). After serving in the US Army from 1969 to 1971, he was with ATT Bell Laboratories from 1973 . From 1988 to 1996 he headed the Mathematical Foundations of Computing department and then the Algorithms and Optimization department . In 1978 he was visiting professor at Rutgers University and in 1980/81 at the University of Wisconsin .
From 1996 to 2004 he was on the council of the Association for Computing Machinery (ACM) (of which he had been a fellow since 1994) and from 1987 to 1991 chaired ACM SIGACT, whose Distinguished Service Award he received in 1997. From 1983 to 1987 he was editor of the Journal of the ACM and from 1991 to 2006 of ACM Transactions on Mathematical Software (TOMS). From 1979 to 2004 he was editor of the Journal of Algorithms, since 1984 of Algorithmica and from 1980 to 1997 of Mathematical Programming and Mathematics of Operations Research. Since 2004 he has been co-editor of ACM Transactions on Algorithms. In the Journal of Algorithms he had a column on algorithms from 1982 to 1992, continued in the ACM Transactions on Algorithms. He is the founder of the ACM SIAM Symposium on Discrete Algorithms (SODA).
In 2005 he became an ATT Fellow and in 2009 a SIAM Fellow.
In 2010 he was awarded the Knuth Prize for early work on NP-completeness and Approximierungsalgorithmen for optimization and search tasks, including NP-hard problems such as the Traveling Salesman Problem and the container problem (Bin Packing). He also wrote a standard work about it with Michael Garey. He not only examined the algorithms for optimization tasks theoretically, but also developed test procedures to assess their performance.
He was married and had one child.
Awards and honors
- 1979: Frederick W. Lanchester Prize
- 1983: Distinguished Technical Staff Award from ATT Bell Laboratories
- 2010: Knuth Prize
- 2016: Admission to the National Academy of Engineering
Fonts
- with Michael Garey Computers and Intractability: a guide to the theory of NP completeness , Freeman, San Francisco 1979
Web links
- Homepage
- Knuth Prize for Johnson
- Linda Crane, In Memoriam David S. Johnson, Columbia University 2016
Individual evidence
- ^ The NP Completeness Column
- ^ Frederick W. Lanchester Prize. (No longer available online.) Informs.org ( Institute for Operations Research and the Management Sciences ), archived from the original on October 2, 2015 ; accessed on February 16, 2016 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.
| personal data | |
|---|---|
| SURNAME | Johnson, David Stifler |
| ALTERNATIVE NAMES | Johnson, David S. |
| BRIEF DESCRIPTION | American computer scientist |
| DATE OF BIRTH | December 9, 1945 |
| PLACE OF BIRTH | Washington, DC |
| DATE OF DEATH | March 8, 2016 |