Past Awards
The Lanchester Prize for 2013 is awarded to David Williamson and David Shmoys for their book,The Design of Approximation Algorithms, Cambridge University Press, New York, 2011.
Solving NP-hard combinatorial optimization problems is of central importance to the field of operations research and the management science, in application domains ranging from network design to scheduling and routing to problems in computational graph theory. Approximation algorithms provide solutions to such problems that are simultaneously provably good and computationally efficient (solvable in polynomial time). This textbook provides a concise and systematic treatment of the major principles of approximation algorithm design, including greedy and local search, rounding data, dynamic programming, deterministic and random rounding of linear programs and semi-definite and primal-dual methods - highlighting the central role that linear and integer programming plays in both the design and analysis of approximation algorithms. This organization by technique rather than by problem area gives an innovative methodological unity to the subject, and the elegance of the authors’ exposition and analyses exemplify the highest traditions of our field.
The Committee members (Garrett van Ryzin, chair, Guillermo Gallego, Steve Gilbert, Martin Rieman, Richard Steinberg, Jan Van Mieghem) are pleased to designate David Williamson and David Shmoys as recipients of the 2013 Lanchester Prize.