Eva Tardos

Eva Tardos
Associate Professor
eva@cs.cornell.edu
http://www.cs.cornell.edu/home/eva/eva.html
Ph.D. Eotvos University, Hungary, 1984

My current research interest focuses on combinatorial optimization problems relevant for the design, maintenance, and management of high-speed communication networks. These networks, the most important communication platform of the future, present new technological challenges. Effective development of future large-scale networks will be impossible without the development of new theoretically sound algorithmic approaches. My research is concerned with developing fast approximation algorithms that can serve as tools for successfully answering these challenges. This year, I worked on two basic problems: finding disjoint paths in graphs (virtual circuit routing) and packet switching.

In a sequence of two papers joint with Jon Kleinberg, we give an O(1) approximation for the maximum disjoint paths problem in densely embedded, nearly-Eulerian graphs, a class of graphs that includes the two-dimensional mesh and many other planar and locally planar interconnection networks. For networks that are not explicitly required to be "high capacity", this is the first constant-factor approximation for the problem in any class of graphs other than trees. We also consider the problem in the on-line setting, relevant to applications in which connection requests arrive over time and must be processed immediately. Here we obtain an asymptotically optimal O(log n)-competitive on-line algorithm for the same class of graphs.

In a paper joint with Yuval Rabani (visiting scientist at Cornell), we developed a new distributed algorithm for the packet switching problem. The packet routing problem is simply that of moving packets in a communication network from their sources to their desired destinations as quickly, as reliably, using as few resources (such as queues) as possible. A solution to this problem consists of two distinct (though by no means independent) parts: a selection of paths for the packets and a schedule of the motion of packets along their selected paths. Earlier, Leighton, Maggs, and Rao considered the second part, the packet scheduling problem when a single packet has to traverse each path. Our results improve the previous results for problems with relatively high dilation (when packets have to travel along long paths in the network). We also extend the techniques to handle the case of infinite streams of regularly scheduled packets along every path.

I also continued my work on algorithms for fundamental problems of combinatorial optimization. The traveling salesman problem was one of the very first problems where the cutting-plano algorithms and the branch-and-cut algorithms were developed and tested. Much of the research has focused on finding new classes of facets for the TSP polytope, and much less attention has been paid to the algorithm to separate among these classes of facets. In joint work with Lisa Fleischer, we consider the problem of finding violated comb inequalities for the traveling salesman problem.

Awards

NSF Presidential Young Investigator 1991-1996
David and Lucille Packard Foundation Fellowship in Science and Engineering 1990-1995

University Activities

Member: Cornell University Engineering Faculty Development Committee; Cornell University Council of Faculty Representatives, 1995; Fields of Operations Research and Applied Mathematics
Head: Requirements Committee for the Center of Applied Mathematics
Faculty Advisor: Tau Beta Pi

Professional Activities

Program Committee Chair: ACM-SIAM Symposium on Discrete Algorithms, 1996
Co-organizer, DIMACS workshop on Architecture and Algorithmic Aspects of Communication Networks, Spring 1997
Program Committee Member: International Mathematical Programming Symposium, 1997
Member: Prize Committee for the ACM Knuth Prize, 1996
Head: Prize Committee for the AMS-Mathematical Programming Society Fulkerson prize, 1997
Council member at large: Mathematical Programming Society, 1994-1997
Editor: SIAM Journal on Computing; Electronic Journal of Theoretical Computer Science; Combinatorica; Mathematical Programming
Associate Editor: Mathematics of Operations Research

Lectures

Separating maximally violated comb inequalities in planar graphs. Integer Programming and Combinatorial Optimization, June 1996 (with L. Fleischer).
Approximation and on-line algorithms for disjoint paths problems. Invited lecture. Summer School on Approximation Algorithms and Combinatorial Optimization, June 1996, Nakenstorf, Germany.
Disjoint paths in densely embedded graphs. Workshop on On-line Algorithms, June 1996, Dagstuhl, Germany.
Distributed packet switching in arbitrary networks. 28th ACM Symposium on Theory of Computing, May 1996 (with Y. Rabani).
Disjoint paths in densely embedded graphs. 34th Annual IEEE Symposium on the Foundations of Computer Science, November 1995 (with J. Kleinberg).
Distributed packet routing in networks. Computer Science, Cornell University, Ithaca, NY, November 1995.
Approximations for the disjoint paths problem in densely embedded graphs. Computer Science, Cornell University, Ithaca, NY, September 1995.

Publications

Separating maximally violated comb inequalities in planar graphs. Proceedings of Integer Programming and Combinatorial Optimization, June 1996, Springer-Verlag, 475-489 (with L. Fleischer).
Distributed packet switching in arbitrary networks. Proceedings of the 28th ACM Symposium on Theory of Computing, May 1996, 366-375 (with Y. Rabani).
Disjoint paths in densely embedded graphs. Proceedings of the 34th Annual IEEE Symposium on the Foundations of Computer Science, 1995, 52-61 (with J. Kleinberg).
Improved bounds on the max-flow min-cut ratio for multicommodity flows. Combinatorica 15, 3 (1995), 425-434 (with S. Plotkin).
Finding approximate solutions to fractional packing and covering problems. Mathematics of Operations Research 20, 2 (1995), 257-301 (with S. Plotkin and D. Shmoys).
Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50 (1995), 228-243 (with T. Leighton, F. Makedon, S. Plotkin, C. Stein, and S. Tragoudas).

Return to: