Andrew Goldberg

Andrew Goldberg has made fundamental contributions to the design and analysis of algorithms for the most central problems in network optimization. His early work on the maximum-flow and minimum-cost flow problems, in which he devised the push-relabel approach for flow algorithms, changed the basic paradigms in efficient flow computation, and today is taught in undergraduate and graduate courses worldwide. A decade later, his work with Satish Rao broke the O(mn) running time "barrier" for maximum-flow algorithms, and introduced an elegant length-function technique to the analysis of blocking-flow algorithms. His work on shortest path algorithms highlights the interplay between ingenious data-structure design and algorithmic paradigms that are tailored to take full advantage of them.

Goldberg's contributions to the empirical analysis of algorithms has perhaps had an even broader impact than his theoretical work, due to the level of rigor and scale of his analyses, as well as from his publicly available optimization software library. Furthermore, his approach of using empirical work as the springboard for subsequent theoretical analyses, in addition to using theoretical research to motivate empirical analyses, has been a hallmark of his research career. Beyond network optimization, his research on algorithmic mechanisms for the pricing of digital goods was influential at the start of the age of electronic commerce. Most recently, Goldberg has returned to his investigation of shortest-path computations, motivated by the need for methods suitable at the scale required by GPS technology, devising new algorithms with strong theoretical guarantees and stunning practical performance on real-world networks.

In summary, Andrew Goldberg is eminently deserving of the 2011 Farkas Prize awarded by the Optimization Society within the Institute for Operations Research and Management Science.

Prize Committee

Gérard Cornuéjols (Chair), Alexander Shapiro, David Shmoys, Stephen Wright