Optimization II: Approximation and Online Algorithms (WS 10/11)

Basic Information

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

Approximation and Online Algorithms: how can I deal with my incompetence and ignorance?

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.

Lectures

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

Results of final exam

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

If any of you are looking for a M.Sc. thesis assignment, feel free to come and talk to me in Room 305 of the MPI!

More Courses of the Algorithms and Complexity Group