Éva Tardos

Jacob Gould Schurman Professor of Computer Science


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

Eva Tardos

Current Ph.D. students

Past Ph.D. students

Recent Talks and Activities:

Research interest

Algorithms and algorithmic game theory, the subarea of theoretical computer science theory of designing systems and algorithms for selfish users. My research focuses on algorithms and games on networks and simple auctions.  I am mostly interested in designing algorithms and games that provide provably close-to-optimal results.

Books

Some Surveys

Courses

Selected Recent Publications

Simple Auctions

Network Games and extensions

Mechanism Design

Social Networks

Classification

Clustering and facility location

Network Design

Routing Disjoint Paths and Packets in Networks

Scheduling

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

Effective bandwidth

Finding cuts in graphs

Separating cutting planes

Other Miscellaneous papers

 

Older 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.