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ürich. 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.