Lecture time: | Wednesday 10-12 and Friday, 12-14 |
---|---|
Lecture room: | 023, Campus E 1.4 |
Lecturers: | Chien-Chung Huang,Rob van Stee |
Tutorial time: | Friday 17-18 |
Tutorial room: | 023, Campus E 1.4 |
Tutor: | Fidaa Abed |
Audience: |
The course counts as computer science lecture (6 SWS, 9 CP).
The lecture will be given in English. |
Schedule: |
The first lecture will take place on Tuesday, October 19.
|
Exercises: | We will hand out exercises every other week. These will count towards your grade. |
Final Exam: |
THURSDAY Feb 10, 12:00-14:00, room 023
|
Re-Exam: | Thursday Mar 31, 14:00-16:00, room 023
|
Book: | Approximation Algorithms, Vijay Vazirani |
There are many practical problems that cannot be perfectly solved or for which it would take too long to find an optimal solution. An example of such a problem is bin packing, where objects are to be packed in bins and the goal is to use as few bins as possible.
In such cases we have an interest in developing simple algorithms that give `almost' perfect solutions in a reasonable time. Such algorithms are called approximation algorithms. The running time of an approximation algorithm should be polynomial in the size of the input, and the result should not deviate by more than a certain factor from the optimal solution.
There are also many problems in which decisions need to be made without full knowledge of the future or even the present. For instance in the case of bin packing one would like to at some point close some bins and send them away, while new objects may still arrive. Or, when scheduling jobs on machines, one cannot wait until all jobs have arrived before starting to allocate jobs to machine and to run them.
How should one make decisions in such cases?
This is the second central question we consider in this course. We will present online algorithms, that deliver good solutions without knowing the future.
Date | Topic | Reference | Homework | Lecturer |
---|---|---|---|---|
Oct 19 | Introduction | Section 1.1.1, Section 9.0 | Huang, van Stee | |
Oct 21 | Metric Traveling Salesman | Section 3.2 | Huang | |
Oct 27 | Multiway Cut, K-cut | Section 4 | Huang | |
Oct 28 | Set Cover and Application | Section 2.1, Section 2.3 | First Assignment | Huang |
Nov 3 | Weighted Vertex Cover | Section 2.2 | Huang | |
Nov 5 | Introduction to Linear Programming | Section 14.1, Section 14.3 | Huang | |
Nov 10 | The skiing cow | Assignment 2 | van Stee | |
Nov 12 | Knapsack | Section 8.1, 8.2 | Huang | |
Nov 17 | List Update | van Stee | ||
Nov 19 | Paging | van Stee | ||
Nov 24 | Bin packing | Assignment 3 | van Stee | |
Nov 26 | -- no class -- | |||
Dec 8 | Bin packing | van Stee | ||
Dec 10 | Online load balancing | van Stee | ||
Dec 8 | Linear programming | Assignment 4 | van Stee | |
Dec 10 | The primal-dual method for online algorithms | van Stee | ||
Dec 15 | Bin Packing | Section 9 | Huang | |
Dec 17 | Minimum Makespan Scheduling | Section 10 | Assignment 5 | Huang |
Jan 5 | Minimum Multi-Cut | Section 18 | Huang | |
Jan 7 | K Median | This paper | Huang | |
Jan 12 | Maximum Satisfiability | Section 16 | Huang | |
Jan 14 | Feedback Arc Set | This paper | Huang | |
Jan 19 | k-server | Assignment 6 | van Stee | |
Jan 21 | k-server | van Stee | ||
Jan 26 | k-center | van Stee | ||
Jan 28 | k-center | van Stee | ||
Feb 2 | Maximizing minimum load | van Stee | ||
Feb 4 | Stable marriage | Huang |
Number | Exercises | Final exam | Grade |
---|---|---|---|
2530689 | 86 | 32 | 1.3 |
2534438 | 99 | 20 | 2.3 |
2535205 | 119 | 35 | 1.0 |
2534786 | 104 | 28 | 1.3 |