ALGORITHMIC ASPECTS OF COMMUNICATION NETWORKS
OR 739: Selected Topics in Optimization
Spring 1997
Time and place:
- MWF 1:25-2:15 pm.
- Phillips 403.
Instructor:
- Eva Tardos, 5144 Upson Hall, 255 0984,
email: eva@cs.cornell.edu .
- Office hours, Monday 2:30-3:30, Wednesday 1030-11:30, or by appointment.
Support Staff:
- January 20, general introduction
- Lecture 2, January 22
- Lecture 3, January 24
- January 27 cancelled
- Lecture 4, January 29
- Lecture 5, January 31
- Lecture 6, February 3
- Lecture 7, February 5
- Lecture 8, February 7
- Lecture 9, February 10
- Lecture 10, February 12
- Lecture 11, February 14
- Lecture 12, February 17
- Lecture 13, February 19
- Lecture 14, February 21
- Lecture 15, February 24
- Lecture 16, February 26
- Lecture 17, February 28
Latex macros for the lecture notes.
- Assignmnent 1 , due Friday, February 7
Correction: The following sentence should have been added to
Problem 2: You may make any assumption about what k is, that helps you.
- Assignmnent 2 , due Friday, February 21
Papers are in the order we discussed them in lecture.
-
Competitive Routing of Virtual Circuits in ATM Networks survey
paper by S. Plotkin,
-
Throughput competitive on-line routing by B. Awerbuch,
Y. Azar and S. Plotkin,
-
On-line machine scheduling with applications to load balancing and virtual
circuit routing by J. Aspnes, Y. Azar, A. Fiat, S. Plotkin and O. Waarts.
- Competitive non-preemptive call control. B. Awerbuch, Y. Bartal, A. Fiat,
and A. Rosen. In Proceedings of ACM-SIAM 5th Annual Symposium on Discrete
Algorithms (SODA) 1994.
-
On-line Admission Control and Circuit Routing in High Performance
Computing and Communications by B. Awerbuch, R. Gawlick, F.T. Leighton,
and Y. Rabani.
- Disjoint Paths in Densely Embedded Graphs
by J. Kleinberg and E. Tardos.
-
Faster approximation algorithms for the unit capacity concurrent flow
problem with applications to routing and finding sparse cuts.
P. Klein, S. Plotkin, C. Stein and E. Tardos. In SIAM Journal on
Computing, 23/3, 1994,. 466-487.
- T. Radzik: Fast Deterministic Approximation for the Multicommodity Flow
Problem, in the Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms, 1995, pp. 486-492.
-
Routing and Admission Control in General Topology
Networks with Poissin Arrivals by O. Palmon, A. Kamath, and S. Plotkin.
- Allocating Bandwidth for Bursty Connections,
by J. Kleinberg, Y. Rabani and E. Tardos.
High-speed integrated networks supporting a variety of heterogeneous
applications will soon become a reality. The size of the future networks,
combined with the need for bandwidth reservation and quality-of-service
guarantees poses numerous challenging problems. 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.
Recent advances in theoretical computer science and discrete mathematics bring
us closer to being able to address many of these issues. In this class
we will discuss these developments.
Students will be expected to do a few homework sets, participate in class,
and take lecture notes.