2003 Tucker Prize Citation

At the XVIII. Mathematical Programming Symposium in Copenhagen the Tucker Prize for an outstanding paper authored by a student has been awarded to Tim Roughgarden, Cornell University, for his thesis ``Selfish Routing''.

Tim Roughgarden, who obtained his BS and MS degrees from Stanford University completed his PhD thesis in May 2002 under the guidance of Eva Tardos. Currently, Dr. Roughgarden continues his work at Cornell University as a postdoc. His thesis considers the classic problem of designing traffic networks that lead to good global routings even when the users are making local, suboptimal decisions. This touches on several disciplines such as game theory, network flows, complexity analysis, approximation algorithms, and economics. Roughgarden analyzes the ``price of anarchy'', i.e., the gap between a socially-optimal global solution and the solution resulting from selfish users, and finds a variety of tight results on what is achievable with reasonable amounts of computation. He further broadens this out to models of other situations with selfish users.

The other two Tucker Prize finalists chosen by this year's Tucker Prize Committee consisting of Rainer Burkard (Chair), Thomas McCormick, Jos Sturm and Leslie Trotter are Pablo Parrilo and Jiming Peng.

Pablo Parrilo obtained his first degrees in Electronic Engineering from the University of Buenos Aires. He obtained a PhD in Control and Dynamical Systems from California Institute of Technology in June 2000 under the guidance of John Doyle. Currently, Dr.Parrilo is Assistent Professor of Analysis and Control Systems at ETH Z\"urich. Dr.Parrilo was nominated as Tucker Prize finalist for his paper ``Semidefinite programming relaxations for semialgebraic methods''. This work establishes a bridge between convex optimization and real algebraic geometry, which opens up a new and promising research area. The main idea is to explore conditions under which a function can be proved to be non-negative by showing that it is a sum of squares. Parrilo shows applications of this in diverse areas such as non-convex quadratic programming, matrix copositivity, linear algebra, and control theory.

Jiming Peng was born in Hunan Province, China. He obtained his first degrees in China. In 1997 Peng moved to Delft University of Technology where he received his PhD for his prize winning thesis entitled ``New Design and Analysis of Interior-Point Methods''. His thesis was guided by C. Roos and T. Terlaky. Peng's work goes a long way to closing the gap between the superior theoretical performance of short-step interior-point methods, and the superior practical performance of long-step methods. Peng does this by inventing a new class of barrier functions called ``self-regular'' which allow long-step methods to be implemented with theoretical time bounds very close to short-step methods. He applies this to linear, complementarity, second-order cone, and semi-definite problems. Currently, Dr.Peng joined the Department of Computing and Software, McMaster University, as an Assistent Professor.