2006 Dantzig Prize Citation
Eva Tardos has made pioneering contributions to mathematical programming. In the
1980s, she solved a longstanding open problem by finding a strongly polynomialtime algorithm for
minimumcost flow. That is, all prior polynomialtime algorithms had a running time that depends on
the number of bits in the costs or the capacities of the input, and her approach was the first to have
a running time that was polynomially bounded solely in terms of the number of nodes of the graph. Most
subsequent work on minimumcost flows, including several of the currently fastest algorithms, has
roots in her revolutionary method.
She has obtained many other important contributions that had significant impact in a wide range of
areas of mathematical programming, including several variants of network flows, integer programming,
submodularity, circuit complexity, scheduling, approximation algorithms, and algorithmic game
theory.
A wide range of network flow models can be viewed as special cases of linear programming, and hence
can be seen to be polynomially solvable by virtue of the fact that linear programming can be solved in
polynomial time. Tardos made significant advances in the design of more efficient polynomialtime
algorithms for these problems that exploit the network structure of the problem. Among these is the
first socalled ``combinatorial'' polynomialtime algorithm for the (generalized) network flow problem
with losses and gains, where there is a loss factor gamma for each arc such that the number of units
of flow leaving an arc is gamma times the number that entered it. She developed algorithms for flows
over time, and for multicommodity flow problems, such as the maximum concurrent flow problem, where
one wishes to maximize the common fraction of each demand that can be routed from its source to the
sink subject to the overall edge capacity constraints in a given network. This work led to further
generalizations for a wide array of combinatoriallydefined linear programs, generally known as
fractional packing and covering problems.
Tardos has been a leader in the use of sophisticated mathematical programming techniques in the
design of approximation algorithms for NPhard discrete optimization problems. This work has had an
impact on a broad crosssection of problems in network design, scheduling, facility location,
clustering, balanced graph cuts, disjoint paths in graphs, and the metric labeling problem (which has
several applications, for example, in machine vision problems in recognizing objects in a given
digital image). For example, for the generalized assignment problem, one is given jobs to assign to a
given set of machines, where for each job, both its processing time and the cost of the assignment
depends on the machine to which it is assigned. Tardos showed that any feasible solution to a natural
linear programming relaxation can be rounded to be integer, using a minimumcost bipartite matching
computation, where the resulting solution has no greater cost, and length no more than twice that of
the fractional solution.
Throughout the years, Eva Tardos has renewed herself scientifically by changing the focus of her
work, most recently by laying foundations for new important directions in algorithmic game theory. Her
work showing surprisingly strong performance bounds for "selfish routing" has gained
attention for its crystalization of the notion of the price of anarchy: if we think of an atom of flow
between associated with a user, how much less efficient is a routing solution for which each user
optimizes his own path, as opposed to a centrally designed minimumcost solution that serves the
general good? One statement of her breakthrough result is that the negative effect of allowing users
to selfishly route their traffic is completely offset by building a network of double the
capacity.
Tardos is a highly stimulating and inspiring team member, always willing to cooperate and to
exchange ideas, and often with clever and surprisingly ingenious ideas that turn out to be basis for
subsequent research. She is an enthusing lecturer, has introduced an impressive line of students to
research, wrote many extremely valuable surveys, and, moreover, plays an important role in linking
mathematical programming to computer science. The depth, breadth, originality, and impact of her work
make Eva Tardos to an excellently deserved winner of the Dantzig Prize.
