This year's ADFOCS features three lecturers, each of which will
give three lectures and two exercise sessions. They will be distributed to eight blocks of about four hours.
A typical morning or afternoon block will start with 1 1/2 hours of
lecture, followed by 1 1/2 hours of exercises (in small groups without the lecturers) with
coffee break and an 1 hour discussion of the exercises with the lecturers.
During the exercise periods, the respective lecturer will be around,
as well as some fruits, snacks, and drinks.
There will be an additional slot for the members of the Algorithms and Complexity Group (D1) at MPI
to introduce the different research areas of the group.
All lectures will take place in room HS003 ('Hoersaal 3') at the ground floor of the Computer Science building (Number E1.3 in the campus map) right next to the MPII building (Number E1.4). The exercise sessions and discussions will take place in room 024 at the ground floor of the MPII building.
September 14 Monday 
September 15 Tuesday 
September 16 Wednesday 
September 17 Thursday 
September 18 Friday 


9.0010.30  Tim Roughgarden 
David B. Shmoys 
Yossi Azar 
Yossi Azar 
Tim Roughgarden 
10.3011.00  
11.0013.00  Tim Roughgarden 
David B. Shmoys 
Yossi Azar 
David B. Shmoys 

13.0014.30  
14.3016.00  Yossi Azar 
Tim Roughgarden 
David B. Shmoys 

16.0016.30  
16.3018.30  Yossi Azar 
Tim Roughgarden 
David B. Shmoys 

Evening 
The price of anarchy measures the deterioration in the performance of the system in the presence of strategic users compared with the global optimum. Coordination mechanism is an algorithmic redesign of the system in order to reduce the price of anarchy. We will survey various results in this area and would focus on assigning jobs, owned by strategic agents, to machines. The goal of each agent is to complete its job as early as possible. Here a coordination mechanism is a local policies performed by the machines for processing the jobs such that the performance of the resulting equilibrium is close to the optimum (i.e. reducing the price of anarchy). We demonstrate that the techniques used in designing coordination mechanisms are related to techniques used in approximation and online algorithms.
Finally, we switch gears and discuss questions related to ordering problems motivated by search problems. In particular we discuss minsum set cover and its generalizations.
We survey two uses of approximation measures in the emerging field of algorithmic game theory: quantifying the inefficiency of gametheoretic equilibria, and designing robust auctions for revenuemaximization. We will cover both basic principles and examples, and a few of the latest research results. We will also discuss promising directions for future research.
One of the most active areas of research in the design of approximation algorithms is for discrete stochastic optimization problems, with a particular focus on 2stage problems with recourse. Here, we are given a probability distribution over inputs, and the aim is to find a feasible solution that minimizes the expected cost of the solution found (with respect to the input distribution); an approximation algorithm finds a solution that is guaranteed to be nearly optimal. Techniques initially developed in the context of deterministic approximation, including rounding approaches, primaldual algorithms, as well as random sampling techniques, have proved to be important in this context as well.
We will survey a number of results in this area, with the aim of showing the range of algorithmic techniques that have been exploited in this setting. In particular, we will show several results that rely on LProunding, including a stochastic variant of the set covering problem and the closely related uncapacitated facility location problem; for primaldual results, we will focus on the problem of scheduling the maximumweight set of ontime jobs; and for random sampling techniques, we will focus on the a priori traveling salesman problem. Furthermore, since an LProunding procedure requires solving the linear relaxation first, we will also discuss techniques for solving these exponentiallylarge linear programs, one of which relies on an analysis of the sample average approximation that can be applied to the discrete versions of many of these problems, as well as their relaxations.