2006 Dantzig Prize Citation

Eva Tardos has made pioneering contributions to mathematical programming. In the 1980s, she solved a long-standing open problem by finding a strongly polynomial-time algorithm for minimum-cost flow. That is, all prior polynomial-time 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 minimum-cost 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 polynomial-time algorithms for these problems that exploit the network structure of the problem. Among these is the first so-called ``combinatorial'' polynomial-time 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 combinatorially-defined 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 NP-hard discrete optimization problems. This work has had an impact on a broad cross-section 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 minimum-cost 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 minimum-cost 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.