236605
Advanced Topics in Computer Science

236605 is a graduate course given at the Technion's Computer Science Department. The topics studied vary from year to year. The Y2K Spring Semester course presents scheduling algorithms.

Prerequisites: computability theory (236343).

The course will discuss the design and analysis of algorithms for scheduling problems. The emphasis is on algorithms whose performance can be analysed rigorously. The lectures are organized to highlight algorithmic methods and their application to a wide variety of scheduling problems.

Teaching Staff:

Lecturers: Prof. Allan Borodin and Dr. Yuval Rabani
Teaching assistant: Mr. Moni Shahar

Prof. Borodin is visiting us from the University of Toronto. He will teach about one third of the classes. His lectures will be in English.

Meets on: Thursdays, 14:30-17:30, Taub 4.

Course requirements: The final grade will be based on evaluation of homework assignments solutions (70%), and scribe notes (30%). You will get further instructions on both. We require students to read and understand, by mid-semester, the linear programming notes that we will hand out in class. These can also be downloaded, see below.


Tentative Syllabus


Lectures

Lecture 1: Introduction. Motivation, examples, notation, optimization, P vs. NP, approximability, on-line vs. off-line, course outline.
Handouts: administrivia, assignment 1.
Recommended reading: KSW 1, 2.1.1-2.

Lecture 2: Greedy algorithms, EDD, SPRT, Johnson's rule, least-cost-last, McNaughton's rule, Graham's LS rule.
Lecture notes (.tex, figures: lmax.tex, ls.tex).
Recommended reading: KSW 2.1.3, 2.2, 2.3.1-2.

Lecture 3: LS for P|prec,r_j|C_max, Graham's LPT rule, greedy and on-line algorithms, interval scheduling.
Lecture notes (.tex, figures: fig1.eps, opt_lpt.eps, another_greedy.eps).
Recommended reading: KSW 2.3.3-4.

Lecture 4: On-line algorithms for P||C_max, Q||C_max, and R||C_max, on-line lower bounds, randomness.
Lecture notes (.tex).
Handouts: assignment 2.
Recommended reading: BE 12.

Lecture 5: Polynomial time approximation schemes and dynamic programming, 1|r_j|L_max.
Lecture notes (.tex).
Recommended reading: KSW 6.3.

Lecture 6: Polynomial time approximation schemes for KNAPSACK, 1||sum w_j U_j, and P||C_max.
Lecture notes (.tex).
Recommended reading: Sahni (1975), Ibarra & Kim (1975), KSW 6.1-2, Hochbaum & Shmoys (1987).

Lecture 7: Polynomial time approximation schemes for P||sum M_i^2 and P||sum w_j C_j.
Lecture notes (.tex).
Handouts: assignment 3.
recommended reading: Alon-Azar-Woeginger-Yadid (1998), Skutella & Woeginger (1999).

Lecture 8: P||sum w_j C_j (continued), R||sum C_j.
Lecture notes (.tex, figure: l8fig1.eps).
recommended reading: Skutella & Woeginger (1999), KSW 4.1.1.

Lecture 9: Using graph algorithms (matching, flows): special cases of R||C_max, P|p_j=d_j-r_j|sum w_j Ubar_j, O|pmtn|C_max; hardness results for R||C_max.
Lecture notes (.tex, figures: l9fig1.eps, l9fig2.eps, l9fig3.eps).
recommended reading: KSW 4.1, Arkin & Silverberg (1987) Lenstra-Shmoys-Tardos (1990).

Lecture 10: R|pmtn|C_max, R||C_max
Lecture notes (.tex). (unavailable yet)
recommended reading: KSW 4.2, Lawler & Labetoulle (1978), Lenstra-Shmoys-Tardos (1990).

Lecture 11: 1|prec|sum w_j C_j, etc.
Lecture notes (.tex).
recommended reading: KSW 5.3, Hall-Schulz-Shmoys-Wein (1997).

Lecture 12: Primal-dual algorithms.
Lecture notes (.tex). (unavailable yet)
Handouts: assignment 4.
recommended reading: .

Lecture 13: Convex programming: R||sum w_j C_j.
Lecture notes (.tex).
recommended reading: Skutella (1999).


Resources

Linear programming notes (postscript file, in Hebrew).
Scribe notes .sty header file
Scheduling Algorithms, a survey paper by Karger, Stein, and Wein.
Complexity Results for Scheduling Problems, a site classifying the complexity of scheduling problems by Brucker and Knust.
Polynomial time approximation algorithms for machine scheduling: Ten open problems, by Schuurman and Woeginger.
On-Line Scheduling, a survey paper by Sgall.
Online Computation and Competitive Analysis, by Borodin and El-Yaniv, Cambridge University Press, 1998.
Journal of Scheduling, John Wiley & Sons, Inc.