Éva Tardos

Jacob Gould Schurman Professor

Research Focus

Algorithmic game theory is an emerging new area of designing systems and algorithms for selfish users. My research focuses on algorithms and games on graphs or networks. I am mostly interested in designing algorithms and games that provide provably close-to-optimal results.

Publications

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

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

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.

Other Miscellaneous papers

Top