Download slides here (gzipped PostScript file).
The first part of the talk focused on the Disjoint Paths Problem: do there exist disjoint paths connecting a given set of source-sink pairs in a given network? Different variants of the problem were described, varying according to allowed interference of paths (node/edge -disjoint versions). Most of the talk centered on optimization versions of the problem. Two particular objectives discussed were (1) admission control: route as many of the source/sink pairs via disjoint paths and (2) congestion control: route all pairs and minimize the maximum number of paths using an edge (this quantity is called congestion). Since all variants are NP-hard, approximation algorithms are considered.
Two more ways to modify the problem:
The online problem reminds of Nemhauser's talk and airline recovery problems, but the different versions (online/offline) of routing problems are very interrelated and most frequently same techniques are applicable.
Clarifications of some slides:
The next part of the talk, on finding disjoint paths on the mesh, is a survey of the papers of Kleinberg and Tardos, available here
The second part of the talk was on the Packet Scheduling problem: given a set of packets with their respective origins and destinations, schedule the motion of packets in time. Some requirements are that
Some papers referred to in the talk:
Prabhakar Raghavan and Clark D. Thompson Randomized Rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, Vol. 7, 1987.
Prabhakar Raghavan and Clark D. Thompson Multiterminal global rounding: A deterministic approximation scheme, Algorithmica, Vol 6, pp 73--82, 1991.
Philip Klein and Serge Plotkin and Clifford Stein and Eva Tardos: Faster Approximation Algorithms for the Unit-Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts. SIAM J. Comput. 23 (1994), no. 3, 466--487.
B. Awerbuch and Y. Azar and S. Plotkin Throughput-competitive online routing 34th IEEE Symposium on Foundations of Computer Science, 1993.
Naveen Garg and Vijay V. Vazirani and Mihalis Yannakakis Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees Algorithmica, 18(1), pp. 3-20, May 1997.
B. Awerbuch and R. Gawlick and T. Leighton and Y. Rabani On-Line Admission Control and Circuit Routing for High Performance Computing and Communication Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 412-423, IEEE Computer Society Press, November 1994.
Jon Kleinberg and Éva Tardos Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pp. 26-35, 29 May - 1. jun 1995.
Jon Kleinberg and Eva Tardos Disjoint Paths in Densely Embedded Graphs 36th Annual Symposium on Foundations of Computer Science (FOCS'95), pp. 52-61, IEEE Computer Society Press, October 1995.
Andrei Z. Broder and Alan M. Frieze and Stephen Suen and Eli Upfal An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 261-268, ACM/SIAM, 28-30* January 1996.
Anil Kamath and Omri Palmon and Serge Plotkin Routing and Admission Control in General Topology Networks with Poisson Arrivals Journal of Algorithms, 27(2), pp. 236-258, May 1998.
Tom Leighton and Bruce Maggs and Satish Rao Universal Packet Routing Algorithms (Extended Abstract) 29th Annual Symposium on Foundations of Computer Science, pp. 256-269, 24-26 October 1988.
Yuval Rabani and Éva Tardos Distributed Packet Switching in Arbitrary Networks Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pp. 366-375, 22-24 May 1996.
Matthew Andrews and Antonio Fernández and Mor Harchol-Balter and Tom Leighton and Lisa Zhang General Dynamic Routing with Per-Packet Delay Guarantees of $O(\textdistance + 1 / \textsession rate)$ 38th Annual Symposium on Foundations of Computer Science, pp. 294-302, 20-22 October 1997.
T. Leighton and B. Maggs Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules Proceedings of the 28th Annual Hawaii International Conference on System Sciences. Volume 2: Software Technology, pp. 555-563, IEEE Computer Society Press, January 1995.