Personal History - Michael R. Garey

Mike Garey is Director of Mathematical Sciences Research at Bell Laboratories, a position he took on in 1988, effectively bringing to a close a 20-year research career in computational complexity, the design and analysis of efficient optimal and ``near optimal'' combinatorial algorithms, the theory of NP-completeness, graph theory, and scheduling theory. And there's no going back once the rust sets in!

Mike initially joined Bell Labs in 1970, at a time when there were no fax machines or VCRs, the Vietnam war was being fought, and fought over, and the Bell System was in flower. He came with a brand new Ph.D. in Computer Science from the University of Wisconsin (his home state). His thesis, on "Optimal binary decision trees for diagnostic identification problems." was written under E. F. Moore (formerly of Bell Labs, and the Moore of the Mealy-Moore automaton model). Mike's first office was just down the hall from his current one.

For eleven years he blithely engaged in proving theorems, inventing algorithms, and writing papers for the usual cast of conferences and journals, with nary a care in the world. A high point of this period was the creation of the book, Computers and Intractability: A Guide to the Theory of NP-Completeness, written with his friend and colleague, David Stifler Johnson. The colon in the title was Mike's idea. ORSA gave the two co-conspirators the 1979 Lanchester Prize for their book, along with a nice lunch at the Broadmoor in Colorado Springs. In 1981, Mike became Department Head for Mathematical Foundations of Computing, a new department derived from part of one previously headed by Ron Graham. It began with David Johnson, Shen Lin, Frank Hwang, Fan Chung, Ed Coffman, and Bob Tarjan, and eventually added a few people like Peter Shor and Narendra Karmarkar. It was an OK group. Department heading in those days was at best a half time job, so Mike still got to do technical work. See his publication list for evidence of this.

Mike began his involvement with professional service in 1975 with a three-year stint as Area Editor for Combinatorics and Graph Theory of the Journal of the ACM (Association for Computing Machinery), followed by a more arduous three years in the role of Editor-in-Chief of the JACM. It was a good experience for learning how to say ``no.'' This began a deeper volunteer involvement with ACM, eventually leading to being first chair of the ACM Doctoral Dissertation Award Committee (1982), three years as chair of the Publications Planning Committee (1983-86), and several terms on the ACM Council as a Member at Large (1988-96). Mike was named a Fellow of the ACM in 1995. Mike also served on the DIMACS Executive Committee during its formative years (1989-1994). In 1989 he was elected as an industrial lab representative to the Executive Board of the Computing Research Association, giving him for the first time a chance to attend all those great meetings he had heard about for so many years in Snowbird, Utah. Unfortunately, those particular meetings happen only once every two years. In 1991 he was elected CRA Treasurer, a role in which people still seem to trust him for some reason.

Mike is married to the former Jenene Gail Brandt (now Garey; those were pre-liberation days), a relationship that began in their senior years at fiercely competitive high schools in the neighboring towns of Manitowoc and Two Rivers, WI. They were married in 1965, between their sophomore and junior years in college, while both were still teenagers (barely). Jenene's dad, a police chief, was not a fan of teenage marriages. Jenene is now a tenured faculty member in New York University's Nutrition, Food and Hotel Management Department. Together they collect American Arts and Crafts antiques (Stickley, Roycroft, Teco, and the like) from the early 1900's, including furniture, pottery, and prints. Both like to cook, with Mike specializing in desserts, a dangerous hobby. They spend as much time as possible in Two Rivers, WI at their Lake Michigan summer home, originally a U.S. Life Saving Station built during the 1880's. When it was originally decommissioned in the 1940's, it was sold to a state senator for $1 and moved up the beach from where it once stood. Despite its shady history, they still love it.

Up [ Mike Garey | Math Center | Comp. and Math. Res. Div. | Bell Labs | Lucent Technologies ]