Michael Randolph Garey (born November 19, 1945) is a

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

researcher, and co-author (with David S. Johnson) of ''

Computers and Intractability ''Computers and Intractability: A Guide to the Theory of NP-Completeness'' is a textbook by Michael Garey and David S. Johnson. It was the first book exclusively on the theory of NP-completeness and computational intractability. The book feature ...

: A Guide to the Theory of

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

ness''. He and Johnson received the 1979

Frederick W. Lanchester Prize The Frederick W. Lanchester Prize is an Institute for Operations Research and the Management Sciences prize (U.S. $5,000 cash prize and medallion) given for the best contribution to operations research and the management sciences published in Engli ...

from the

Operations Research Society of America The Institute for Operations Research and the Management Sciences (INFORMS) is an international society for practitioners in the fields of operations research (O.R.), management science, and analytics. It was established in 1995 with the merger of ...

for the book. Garey earned his PhD in

in 1970 from the

University of Wisconsin–Madison The University of Wisconsin–Madison (University of Wisconsin, Wisconsin, UW, UW–Madison, or simply Madison) is a public land-grant research university in Madison, Wisconsin, United States. It was founded in 1848 when Wisconsin achieved st ...

. He was employed by

AT&T Bell Laboratories Nokia Bell Labs, commonly referred to as ''Bell Labs'', is an American industrial research and development company owned by Finnish technology company Nokia. With headquarters located in Murray Hill, New Jersey, Murray Hill, New Jersey, the compa ...

in the Mathematical Sciences Research Center from 1970 until his retirement in 1999. For his last 11 years with the organization, he served as its director. His technical specialties included discrete algorithms and

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

scheduling theory In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows. The scheduling activity is carried out by ...

, and

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

. From 1978 until 1981 he served as Editor-in-Chief of the ''

Journal of the Association for Computing Machinery The ''Journal of the ACM'' (''JACM'') is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is ...

''. In 1995, Garey was inducted as a

Fellow of the Association for Computing Machinery A fellow is a title and form of address for distinguished, learned, or skilled individuals in academia, medicine, research, and industry. The exact meaning of the term differs in each field. In learned or professional societies, the term refers ...

References

External links

Garey's personal web page
University of Wisconsin–Madison College of Letters and Science alumni 1995 fellows of the Association for Computing Machinery American theoretical computer scientists Living people 1945 births American textbook writers {{compu-scientist-stub