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 sociallyoptimal 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 nonnegative by showing that it is a sum of
squares. Parrilo shows applications of this in diverse areas such
as nonconvex 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 InteriorPoint 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 shortstep interiorpoint methods, and the superior practical
performance of longstep methods. Peng does this by inventing a
new class of barrier functions called ``selfregular'' which allow
longstep methods to be implemented with theoretical time bounds
very close to shortstep methods. He applies this to linear, complementarity,
secondorder cone, and semidefinite problems. Currently, Dr.Peng
joined the Department of Computing and Software, McMaster University,
as an Assistent Professor.
