Eva Tardos Professor eva@cs.cornell.edu http://www.cs.cornell.edu/home/eva/eva.html PhD Eotvos Univ., Hungary, 1984 My research interest focuses on the design and analysis of efficient methods for combinatorial optimization problems on graphs or networks. I am mostly interested in fast combinatorial algorithms that provide provably close-to-optimal results for NP-hard problems. An important area of applications is the design, maintenance, and management of high-speed communication networks. These networks, the most important communication platform of the future, present new technological challenges.

The essence of many of these technological problems is the intractability of certain simple network problems, such as routing, bandwidth allocation, packet scheduling, and network design. My research goal is to develop methods to deal with these simple network problems; these algorithms can serve as tools for successfully answering the new technological challenges.

I spent the most time working on the disjoint paths problem, the combinatorial essence of the routing problem. This problem is important for its applications to large-scale communication networks, but it is also one of the most basic algorithmic questions (it is one of Karp's original NP-complete problems) and has been studied extensively since the 1960's. Despite a lot of work, there is very little known about finding close-to-optimal routing in general classes of networks.

Two other areas that I have worked on are the bandwidth allocation problem and network design. J. Kleinberg, Y. Rabani and I undertook the first study of the issues inherent in statistical multiplexing from the perspective of approximation algorithms.

Awards

ACM Fellow 1998

University Activities

• Fields of Operations Research and Applied Mathematics

• Membership committee, Center for Applied Math

Professional Activities

• Program Committee Member: Int. Mathematical Programming Symp., 1997 DIMACS External Advisory Board 1996-1999

• Editor: SIAM J. Computing, Electronic J. Theoretical Computer Science, Combinatorica

• Associate Editor: Mathematics of Operations Research, Mathematical Programming A

Lectures

• Flows in networks. Invited Lecture, SIROCCO'98, June 1998.

• Flows in networks. Invited lecture, DIMACS workshop on large scale optimization, May 1998.

• Using linear programming in approximation Algorithms. Budapest, March 1998.

• Routing in networks. Invited Semiplanary lecture, Mathematical Programming Symp., Lausanne, Aug. 1997. Simple maximum flow algorithms in lossy networks, Symp. Integer Programming and Combinatorial Optimization (IPCO), June 1998.