Monday 19

Klaus Jansen ( University of Kiel )

Approximation algorithms for scheduling problems with precedence constraints
1. Introduction (problem definitions, complexity, inapproximability)
2. Basic techniques (list scheduling, linear programming relaxations)
3. Scheduling with communication delays (algorithm by Hanen and Munier)
4. Scheduling malleable tasks (algorithm by Lepere, Trystram and Woeginger)

 Tuesday 20

Ingo Schiermeyer ( University of Freiberg )

Exact and approximation algorithms for k-Colourability and Maximum Independent Set
1. NP-completeness and NP-hardness
2. Nonapproximability results
3. Lower and upper bounds for the chromatic number and the independence number
4. Exact (exponential time) algorithms
5. Approximation (polynomial time) algorithms
6. Exact polynomial time algorithms based on forbidden induced subgraphs

 Wednesday 21

(excursion in the afternoon)

Roberto Solis-Oba (University of Western Ontario )

Approximation algorithms for facility location and k-median problems
- Linear programming based algorithms
  Filtering
  Rounding
- Primal-dual algorithms
  Algorithm of Jain and Vazirani
- Local optimization
  Algorithm of Arya, Garg, Khandekar, Meyerson, Munagala, and Pandit.

 Thursday 22

Martin Skutella (MIT)

Flows Over Time

The intention of the lecture is to give an introduction into the area of "flows over time" or "dynamic flows." Flows over time have been introduced about forty years ago by Ford and Fulkerson and have many real-world applications such as, for example, traffic control, evacuation plans, production systems, communication networks, and financial flows. Flows over time are modeled in networks with capacities and transit times on the arcs. The transit time of an arc specifies the amount of time it takes for flow to travel from the tail to the head of that arc. In contrast to the classical case of static flows, a flow over time specifies a flow rate entering an arc for each point in time and the capacity of an arc limits the rate of flow into the arc at each point in time. The topics covered range from the classical results of Ford and Fulkerson on maximal s-t-flows over time to very recent approximation results for flows over time with multiple commodities and costs.

 Friday 23

Anand Srivastav ( University of Kiel )

Probabilistic Methods in the Design of Approximation Algorithms

Probabilistic Methods: Large Deviations, Chernoff-Hoeffding Inequalities, Martingales, Sieve-Methods and Lovasz -Local-Lemma and Applications to Integer Programming of Packing and Covering Type, Hypergraph Coloring, Multicast Routing.