INFORMS NEWS: Williamson, Shmoys win Lanchester Prize

Committee Chair Garrett van Ryzin, recipients David Williamson and David Shmoys and INFORMS President Anne Robinson (l-r).

Committee Chair Garrett van Ryzin, recipients David Williamson and David Shmoys and INFORMS President Anne Robinson (l-r).

The 2013 Lanchester Prize was awarded to David Williamson and David Shmoys of Cornell University for their book, “The Design of Approximation Algorithms,” Cambridge University Press, New York, 2011. Committee Chair Garrett van Ryzin presented the award at the 2013 INFORMS Annual Meeting in Minneapolis.

The Lanchester Prize is awarded by INFORMS for the best contribution to operations research and the management sciences published in English in the past three years. The prize includes a commemorative medallion and a $5,000 cash award.

The award citation read in part:

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.

Along with van Ryzin, the prize committee includes Guillermo Gallego, Steve Gilbert, Martin Rieman, Richard Steinberg and Jan Van Mieghem.