Preliminary abstracts for the lectures:

• Thomas Erlebach   (ETH Zurich):  
  Approximation algorithms for geometric intersection graphs

  Approximation algorithms for geometric intersection graphs Intersection graphs of geometric objects (such as disks or squares) have applications in map labeling and cellular communication networks, for example. In this lecture we discuss approximation algorithms for fundamental graph problems like independent set, vertex cover, and dominating set in certain geometric intersection graphs. We will cover simple greedy-based constant-factor approximation algorithms due to Marathe et al.; approximation schemes for unit disk graphs obtained with the classical shifting strategy of Baker, Hochbaum, and Maass; and recent results about approximation schemes for general disk graphs obtained in joint work with Jansen and Seidel and independently by Chan.

• Lisa Fleischer  (Carnegie Mellon University, Pittsburgh) and  Martin Skutella (TU Berlin):  
  Flows over time - efficient algorithms and approximations

  The intention of the two lectures 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 modelled 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 by the two lectures 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.

• Rolf Möhring   (TU Berlin):  
  Approximation algorithms for scheduling under uncertainty

  Deterministic scheduling models usually suffer from the fact that they neglect random influences that occur during project execution. A typical consequence often encountered in practice is the underestimation of the expected project duration and project cost. The area of stochastic scheduling provides methods and tools to cope with these phenomena. I will present recent approximation algorithms to construct scheduling policies that are provably good in expectation. This will include a discussion of how to extend approximation techniques for deterministic problems to problems with uncertainty.

• Uri Zwick   (Tel Aviv University):  
  Semidefinite programming based approximation algorithms

  The lecture will describe the use of semidefinite programming in the development of approximation algorithms for combinatorial optimization problems. The talk will start with a definition of semidefinite programming. No prior knowledge of the subject would be assumed. It will then describe the MAX CUT approximation algorithm of Goemans and Williamson, the major "success story" of the area. The related approximation algorithms for the MAX 2-SAT, MAX DI-CUT and the MAX 3-SAT problems will then be briefly described. Next, we will shortly discuss Lovasz's theta-function, the first application of semidefinite programming in combinatorial optimization. Finally, the algorithm of Karger, Motwani and Sudan for approximate coloring will be described.