Éva Tardos

Professor

Department of Computer Science
4105B Upson Hall
Cornell University
Ithaca, NY 14853
phone: (607) 255-0984
fax: (607) 255-4428
Email: eva@cs.cornell.edu .


Current Activities

  • Courses I taught recently
  • Publications
  • click here to see pictures of my kids.

 

Current Ph.D. students

Past Ph.D. students

Research Interests:

My research is concerned with the design and analysis of algorithms for fundamental problems in network,  combinatorial optimization, approximation algorithms, on-line algorithms, linear and integer programming, and their  applications to various problems.

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  optimal or close-to-optimal results. Such problems find applications in many areas. I am working on problems that are related to the design, maintenance, and management of communication networks; problems that arise from vision; and problems related to the management of electric power networks.

An important area of applications that I am interested in, 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.

Selected Recent Publications

 

Courses and Seminars

Selected Recent Publications

Games on Networks

  • T. Roughgarden and E, Tardos: How Bad is Selfish Routing? In the Proceedings of the 41st Annual IEEE Symposium on the Foundations of Computer Science, 2000. 

Classification

Clustering and facility location

Network Design

Routing Disjoint Paths and Packets in Networks

Scheduling

  • D. Shmoys and E. Tardos, An approximation algorithm for the generalized assignment problem. Mathematical Programming A 62, 1993, 461-474.  Preliminary version has appeared in the proceeding of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993.
  • A. Goel, M. Henzinger, S. Plotkin, and E. Tardos. Scheduling Data Transfers in a Network and the Set Scheduling Problem In the  Proc. of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 189-199.

Generalized Flow

  • A. Goldberg, S. Plotkin, E. Tardos: Combinatorial algorithms for the generalized circulation problem, Mathematics of Operations Research, 16/2, 1991, 351-381. Preliminary version has appeared in the Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science (1988), 432-443.
  • E. Tardos and K. Wayne. Simple Generalized Maximum Flow Algorithms. Proceedings of the 6th International Integer Programming and Combinatorial Optimization Conference   (IPCO'98), Houston, 1998, pp. 310-324.

Packing and Covering Algorithms

  • P. Klein, S. Plotkin, C. Stein and E. Tardos, Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts.  SIAM Journal on Computing, 23/3, 1994,. 466-487. Preliminary version has appeared in the proceedings of the 22nd Annual ACM Symposium on the Theory of Computing (1990), 310-321.
  • T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos, S. Tragoudas: Fast Approximation Algorithms for Multicommodity Flow Problems, Journal of Computer and System Sciences, 50 (STOC'91 special issue), 1995, pp. 228--243. Preliminary version has appeared in the Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (1991), 101-110.
  • S.A. Plotkin, D. Shmoys, and E. Tardos, Fast approximation algorithms for fractional packing and covering problems, to appear in Mathematics of Operations Research. ORIE TR-999Preliminary version has appeared in the Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science (1991), 495-505.

Networks with transit times

  • B. Hoppe and E. Tardos: Polynomial Time Algorithms for Some Evacuation Problems. In the proceeding of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1994, pp. 433-441. ORIE TR-1117.
  • B. Hoppe and E. Tardos: The Quickest Transshipment Problem, journal version of the paper in the proceeding of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 1995 pp. 512-521.
  • L. Fleischer and E. Tardos. Efficient Continuous-Time Dynamic Network Flow Algorithms. Operations Research Letters 23 (1998) pp. 71-80.

Effective bandwidth

Finding cuts in graphs

  • S.A. Plotkin and E. Tardos, Improved Bounds on the Max-flow Min-cut Ratio for Multicommodity Flows. to appear in Combinatorica. Preliminary version has appeared in the Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 691-697. ORIE TR-1042.
  • P. Klein, S. Plotkin, S. Rao and E. Tardos: Approximation Algorithms for Steiner and Directed Multicuts. ORIE TR-1119.

Separating cutting planes

Survey Papers

  • A. V. Goldberg,  E. Tardos, R. E. Tarjan: Network  Flow Algorithms, in   Paths, Flows and VLSI-Design (eds. B. Korte, L. Lovasz, H.J. Proemel, and A. Schrijver) Springer Verlag, 1990, 101-164.
  • E. Tardos: Strongly Polynomial and Combinatorial Algorithms in Optimization, in the Proceedings of the International Congress of  Mathematicians Kyoto 1990, Springer-Verlag, Tokyo 1991, 1467-1478.
  • D. B. Shmoys, E. Tardos: Computational Complexity, In the Handbook of Combinatorics (eds. R. Graham, M. Groetschel, and L. Lovasz) North Holland. An extended version has appeared as Technical Report 918, School of  Operations Research and Industrial Engineering, Cornell University.
  • L. Lovasz, D. B. Shmoys and E. Tardos: Combinatorics in Computer Science,  In the Handbook of Combinatorics (eds. R. Graham, M. Groetschel,  and L. Lovasz) North Holland.
  • E. Tardos: Approximate Min-Max Theorems and Fast Approximation Algorithms for Multicommodity Flow Problems, annotated bibliography.  In Proc. of the Summer School on Combinatorial Optimization, in Maastricht,
    The Netherlands, Aug. 1993.
  • E. Tardos: Approximate Min-Max Theorems and Fast Approximation  Algorithms for Multicommodity Flow Problems, In Proc. Network Optimization  Theory and Practice (NETFLOW), in San Miniato (PI) Italy, Oct. 1993.