max planck institut
informatik

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

## Basic Information

Lecture time: Wednesday 10-12 and Friday, 12-14 023, Campus E 1.4 Chien-Chung Huang,Rob van Stee Friday 17-18 023, Campus E 1.4 Fidaa Abed The course counts as computer science lecture (6 SWS, 9 CP). The lecture will be given in English. The first lecture will take place on Tuesday, October 19. We will hand out exercises every other week. These will count towards your grade. THURSDAY Feb 10, 12:00-14:00, room 023 Thursday Mar 31, 14:00-16:00, room 023 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