Past Awards
The 1979 Lanchester Prize has been awarded to Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael R. Garey and David S. Johnson, published by W. H. Freeman and Company, San Francisco, 1979. The citation for the prize-winning book is as follows:
"For over 30 years operations researchers, practitioners and theoreticians have struggled with a number of difficult combinatorial optimization problems. These problems arise in many important practical applications of operations research and include most of the classical problems from fields like scheduling, location and vehicle routing. In the early 1970's the pioneering work of Steven Cook and Richard Karp showed that most of these problems are intrinsically related and are probably unsolvable in the sense that we are unlikely to ever have algorithms guaranteed to solve large problems optimally with acceptable computational effort. These problems have now come to be called NP-complete.
"The concept of NP-completeness has had a profound influence on research in combinatorial optimization. Almost every paper in the operations research literature on a hard combinatorial optimization problem cites its NP-completeness. Furthermore, as a result of this influence, the direction of research on these problems has shifted to embrace the analytic study of approximation methods in addition to exact optimization. Indeed, this area has even captured the attention of popular audiences. Who could have predicted that the first mention of operations research on the front page of The New York Times would deal with the computational complexity of linear programming?
"This year's Lanchester Prize winner is a book that provides a beautiful exposition of NP-completeness. The authors are major contributors to the literature on this subject and have used this perspective to give an encyclopedic coverage of the area. The book emphasizes those concepts and techniques that are useful in applying the theory of NP completeness to practical problems. It also documents several hundred NP-complete problems from the operations research literature."