É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

• Vardges Melkonian
• Tim Roughgarden
• Aaron Archer

Past Ph.D. students

• Bruce Hoppe
• Lisa Fleischer
• Wee Liang Heng
• Kevin Wayne

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

• Games in Networks
• Classification
• Clustering and facility location
• Network design
• Scheduling
• Routing disjoint paths and packets in networks
• Flows with gains and losses
• Packing and covering problems
• Flows with transit times
• Effective bandwidth
• Finding cuts in graphs
• Separating cutting planes

Courses and Seminars

• Design and Analysis of Algorithms, CS 681, fall 2000
• Introduction to Algorithms, CS 482, spring 1999
• Seminar on Approximation Algorithms, spring 1999
• Theory Seminar, spring 1999
• Mathematical Programming, OR 630, fall 1998
• Optimization,  OR 321, spring 1998
• Data Structures, CS 410, fall 1997

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

• J. Kleinberg and E. Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships:
  Metric Partitioning and Markov Random Fields, In the Proceedings of the 40th Annual IEEE Symposium on the Foundations of Computer Science, 1999.
• A. Gupta, and E. Tardos: A Constant Factor Approximation Algorithm for a Class of Classification Problems, In the Proceedings of the ACM Symposium on the Theory of Computing, May 2000.

Clustering and facility location

• D. B. Shmoys,  E. Tardos and K. Aardal. Approximation algorithms for the facility location problem.
  In the Proc. of the 29th Annual ACM Symposium on the Theory of Computing, 1997, pp. 265-274.
• M. Charikar, S. Guha, E. Tardos and D. Shmoys. A constant-factor approximation algorithm for the k-median problem. In the  Proc. of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 1-10.

Network Design

• M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E. Tardos, and D. Williamson: Improved approximation algorithms for network design problems. In the proceeding of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1994, pp. 223-232. ORIE TR-1116.
• V. Melkonian and E. Tardos. Approximation Algorithms for a Directed Network Design Problem.
  In the Proceedings of the 7th International Integer Programming and Combinatorial Optimization Conference (IPCO'99), Graz, 1999.

Routing Disjoint Paths and Packets in Networks

• J. Kleinberg, Y. Rabani, and E. Tardos. Fairness in Routing and Load Balancing, In the Proceedings of the 40th Annual IEEE Symposium on the Foundations of Computer Science, 1999.
• J. Kleinberg and E. Tardos: Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks, Journal of Computer and System Sciences STOC'95 special issue, vol 57, pp 61-73, 1998. Preliminary version has appeared in the Proceedings of the 27th Annual ACM Symposium on the  Theory of Computing, 1995, pp. 26-35. ORIE TR-1121.
• J. Kleinberg and E. Tardos: Disjoint Paths in Densely Embedded Graphs, In the Proceedings of the 34th Annual IEEE Symposium on the Foundations of Computer Science, 1995, pp. 52-61.
• Y. Rabani and E. Tardos: Distributed Packet Switching in Arbitrary Networks, in the 28th ACM Symposium on Theory of Computing, May, 1996, pp. 366-376.

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-999.  Preliminary 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

• J. Kleinberg, Y. Rabani and E. Tardos. Allocating Bandwidth for Bursty Connection. Journal version of the paper in the Proceedings of the 29th ACM Symposium on Theory of Computing, May, 1997, pp. 664-673.

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

• L. Fleischer and E. Tardos: Separating Maximally Violated Comb Inequalities in Planar Graphs, tech report version of the paper in the Proceedings of the 5th International Integer Programming and Combinatorial Optimization Conference (IPCO), June 1996, pp. 475-489.

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.