Eva Tardos
Biography
Eva Tardos has reshaped and renewed the foundations of algorithm design with long-term vision, creativity, and technical strength that is benefitting the Internet through improved resource allocation, network formation, routing and congestion control, and electronic commerce. During a career spanning over 30 years, Tardos is most known for her work on network-flow algorithms, approximation algorithms, and quantifying the efficiency of selfish routing through the lens of algorithmic game theory. Her solo work on strongly polynomial algorithms was a breakthrough, having resolved a major open problem in the field; in particular, she showed that the minimum-cost flow problem (one of the basic problems in network flow that models the efficient transport of goods through a network) could be solved in strongly polynomial time, with a running time depending only on the number of nodes and edges of the network, not on the magnitudes of its capacities or costs. She then played a pivotal role in establishing the modern use of linear programming in algorithm design to advance the field of approximation algorithms. She has developed approximation algorithms for fundamental problems in a wide range of application areas, including facility location, routing, clustering, classification, and social network analysis.
Tardos’ work has been one of the pillars of algorithmic game theory, a burgeoning field that brings theoretical computer science and economics together to develop algorithmic foundations for our highly connected digital world. Algorithmic game theory is concerned with algorithms designed in the presence of self-interested agents, governed by incentives and economic constraints. Her pioneering work with Tim Roughgarden demonstrated how game-theoretic ideas could quantify the performance gaps between centrally managed network traffic and the flow of traffic directed by self-interested agents. This innovation provided the tools by which computer scientists can analyze the behavior of rational entities in computerized systems and has sparked an enormous amount of further research.
A member of the U.S. National Academy of Sciences and National Academy of Engineering, Tardos is the Jacob Gould Schurman Professor of Computer Science at Cornell University, Ithaca, NY, USA.
