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
 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 HighDiameter Planar Networks, Journal of Computer
and System Sciences STOC'95 special issue, vol 57, pp 6173, 1998. Preliminary
version has appeared in the Proceedings of the 27th Annual ACM Symposium on the
Theory of Computing, 1995, pp. 2635. ORIE TR1121.
 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. 5261.
 Y. Rabani and E. Tardos: Distributed
Packet Switching in Arbitrary Networks, in the 28th ACM Symposium on Theory of
Computing, May, 1996, pp. 366376.
Scheduling
 D. Shmoys and E. Tardos, An approximation algorithm for the generalized assignment
problem. Mathematical Programming A 62, 1993, 461474. Preliminary
version has appeared in the proceeding of the 4th Annual ACMSIAM 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. 189199.
Generalized Flow
 A. Goldberg, S. Plotkin, E. Tardos: Combinatorial algorithms for the
generalized circulation problem, Mathematics of Operations Research, 16/2, 1991,
351381. Preliminary version has appeared in the Proceedings of the
29th Annual IEEE Symposium on the Foundations of Computer Science (1988), 432443.
 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. 310324.
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,. 466487. Preliminary
version has appeared in the proceedings of the 22nd Annual ACM Symposium on the Theory of
Computing (1990), 310321.
 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. 228243. Preliminary
version has appeared in the Proceedings of the 23rd Annual ACM Symposium on the Theory of
Computing (1991), 101110.
 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 TR999. Preliminary version has appeared in the Proceedings of the 32nd Annual
IEEE Symposium on the Foundations of Computer Science (1991), 495505.
Networks with transit times
 B. Hoppe and E. Tardos: Polynomial Time Algorithms for Some Evacuation Problems. In the
proceeding of the 5th Annual ACMSIAM Symposium on Discrete Algorithms, January 1994, pp.
433441. ORIE TR1117.
 B. Hoppe and E. Tardos: The
Quickest Transshipment Problem, journal version of the paper in the proceeding of the
6th Annual ACMSIAM Symposium on Discrete Algorithms, 1995 pp. 512521.
 L. Fleischer and E. Tardos. Efficient ContinuousTime Dynamic Network Flow Algorithms.
Operations Research Letters 23 (1998) pp. 7180.
Effective bandwidth
Finding cuts in graphs
 S.A. Plotkin and E. Tardos, Improved Bounds on the Maxflow Mincut 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. 691697. ORIE TR1042.
 P. Klein, S. Plotkin, S. Rao and E. Tardos: Approximation Algorithms for Steiner and
Directed Multicuts. ORIE
TR1119.
Separating cutting planes

