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.
