Professors Shmoys and Williamson win a top Operations Research prize

“Decisions, decisions.   The difficulty of sifting through large amounts of data in order to make an informed choice is ubiquitous in today’s society.”   So begins The Design of Approximation Algorithms by ORIE Professors David P. Williamson and David B. Shmoys.  The book goes on to tackle a broad array of computationally-supported decision-making problems, ranging from designing low-cost telecommunications networks, to locating facilities, to scheduling jobs on machines. The common themes are discrete optimization (i.e., optimizing among a number of discrete choices, as opposed to a continuum of alternatives) and a quest for solutions that have values that are close to optimal.

The two Cornell professors began work on their graduate-level textbook in the mid-1990s, when Williamson, who has since joined ORIE, was an IBM Research Staff Member.  The book was published in 2011. 

A major award

Now the Institute for Operations Research and the Management Sciences (INFORMS), has awarded the authors the 2013 Lanchester Prize for “the best contribution to operations research and the management sciences published in English in the past three years.”  The prize, first awarded nearly 60 years ago, is considered one of the most prestigious in the profession of operations research.

The award citation from INFORMS notes that The Design of Approximation Algorithms “provides a concise and systematic treatment of the major principles of approximation algorithm design.  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.”

In the book, Williamson and Shmoys quote an old engineering slogan -- “Fast, Cheap. Reliable.  Choose two”-- in suggesting that it may be impossible to develop computational methods that simultaneously (1) finds optimal solutions, (2) finds them in a time that grows more slowly than a power of the size of the problem, and (3) does so for any instance of the problem.  They investigate the implications of choosing two of these criteria by dropping the requirement for a provably optimal solution in favor of finding methods, called approximation algorithms, that relatively quickly find solutions with values within a provably small approximation to the (unknown) optimal value.

Hard computational problems

It may seem surprising with today’s computing power that there are real problems the solutions to which require an impractical amount of computing time.  But in the early 1970’s, Cook, Karp, and Levin gave techniques that provided evidence that optimization problems that are important in scheduling, routing, inventory, and many other fields cannot be solved within a number of steps bounded by a polynomial (such as n2 or n3 + n) in n, the size of the input, as measured by quantities such as the number of points to be served by a telecommunications network, the number of possible facility locations, or the number of jobs and machines to be scheduled.

In other words, computation time would explode as the problem size increases, rendering any computational method impractical even on computers that are a billion times more powerful than when Cook, Karp, and Levin first highlighted their framework for characterizing the computational complexity of a problem.  These problems have become known as “NP-complete”.” a class which includes a wide variety of problems arising in the practical application of operations research. 

Whether any NP-complete problem can be computed in time bounded by a polynomial remains a major open question in mathematics, but if one NP-complete problem can be solved in polynomial time then they all can be.  Pending resolution of this open question, algorithms that provide near-optimal solutions in polynomial time are of substantial practical and theoretical interest.

Relaxing “as little as we possibly can”

In their book, Williamson and Shmoys follow a common approach to NP-complete problems, which is “to relax the requirement for finding an optimal solution, and instead settle for a solution that is ‘good enough’, especially if it can be found in seconds or less.”  This approach typically entails the use of “heuristics” which go by names such as “local search methods”, “greedy approaches”, and “rounding of optimal (fractional) linear programming solutions” that often yield good results in practice. 

Such heuristics are “studied empirically; they might work well, but we might not understand why,” the authors state.  Their “goal is to relax [the requirement of finding an optimal solution] as little as we possibly can,” while providing a “mathematically rigorous basis on which to study heuristics,” to get solutions to discrete optimization problems, to focus on idealized models, to develop metrics that can “distinguish between various optimization problems in terms of how well they can be approximated,” and “because it’s fun.” 

Author backgrounds

Williamson received his MS (supervised by Shmoys) and Ph.D. in computer science at MIT, where he had been an undergraduate, and was a post-doctoral student at Cornell under Professor Éva Tardos before joining IBM Research in Yorktown Heights NY and San Jose CA.   He has won several prizes for his work on approximation algorithms, including the 2000 Fulkerson Prize, which is named after the late ORIE professor D. R. Fulkerson and is sponsored by the American Mathematical Society and the Mathematical Programming Society.

Shmoys was an undergraduate at Princeton and received his Ph.D. in computer science from the University of California at Berkeley.  He joined ORIE from MIT, was recently named the Laibe/Acheson Professor of Business Management & Leadership Studies, is the current Director of ORIE, and is a Fellow of INFORMS, the Society for Industrial and Applied Mathematics, and the Association for Computing Machinery. 

Other recent Cornell winners

The Lanchester Prize has been awarded four times in the past seven years, each time with individuals associated with operations research at Cornell among the recipients.  The 2011 winners were Cornell economics professor David Easley and Jon Kleinberg for their book Networks, Crowds, and Markets.  Kleinberg is a member of the Graduate Field of Operations Research at Cornell.  The three winners in 2008 included Lawrence M. Wein, ORIE ’79 for a series of papers on homeland security, while in 2007 the award went to The Traveling Salesman Problem: A Computational Study, coauthored by Robert E. Bixby, ORIE Ph.D. ’72.