max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

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
Search MPII (type ? for help)