David S. Johnson
David Stifler Johnson ( born December 9, 1945 in Washington, DC) is an American computer scientist.
Johnson studied mathematics at Amherst College (Bachelor in 1967 summa cum laude) and the Massachusetts Institute of Technology, where he 1968 Seymour Papert his master's degree made ( look-ahead strategies in one person games with randomly generated game trees ), and in 1973 Michael J received his doctorate. Fisher ( MIT) (Near optimal bin- packing algorithms ). After serving in the U.S. Army from 1969 to 1971, he was from 1973 at the ATT Bell Laboratories. 1988 to 1996 he headed the Department of Mathematical Foundations of Computing and thereafter, the department Algorithms and Optimization. In 1978 he was a visiting professor at Rutgers University and in 1980/81 at the University of Wisconsin.
1996-2004 he was the Council of the Association for Computing Machinery (ACM ) ( which he is a Fellow since 1994) and stood before 1987 to 1991 of the ACM SIGACT, the Distinguished Service Award he received in 1997. 1983 to 1987 he was editor of the Journal of the ACM and from 1991 to 2006 by ACM Transactions on Mathematical Software ( TOMS ). 1979 to 2004 he was editor of the Journal of Algorithms, 1984 by algorithmica and 1980-1997 of Mathematical Programming and Mathematics of Operations Research. Since 2004 he has been associate editor of the ACM Transactions on Algorithms. In the Journal of Algorithms he had from 1982 to 1992 a column about algorithms, continued in the ACM Transactions on Algorithms. He is the founder of the ACM - SIAM Symposium on Discrete Algorithms ( SODA ).
In 1979 he was awarded the Lanchester Prize of the Operations Research Society of America. He was ATT Fellow and 2009 SIAM Fellow in 2005. In 1983 he received the Distinguished Technical Staff Award from the ATT Bell Laboratories.
In 2010 he received the Knuth Prize. He received the award for early work on NP- completeness and Approximierungsalgorithmen for optimization and search tasks, including NP- hard problems such as the problem of the traveling salesman problem and the container ( bin packing ). He wrote a standard work with Michael Garey. He examined the algorithms for optimization tasks not only theoretically, but also developed test method to evaluate their performance can.
He is married and has one child.
Writings
- Michael Garey Computers and intractability: a guide to the theory of NP complete ness, Freeman, San Francisco 1979