Program

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.

Schedule

	September 14 Monday	September 15 Tuesday	September 16 Wednesday	September 17 Thursday	September 18 Friday
9.00-10.30	Lecture Tim Roughgarden	Lecture David B. Shmoys	Lecture Yossi Azar	Lecture Yossi Azar	Lecture Tim Roughgarden
10.30-11.00	Coffee Break	Coffee Break	Coffee Break	Coffee Break	Coffee Break
11.00-13.00	Exercises Tim Roughgarden	Exercises David B. Shmoys	Exercises Yossi Azar	Talks by members of the MPII	Lecture David B. Shmoys
13.00-14.30	Lunch	Lunch	Lunch	Lunch	Lunch
14.30-16.00	Lecture Yossi Azar	Lecture Tim Roughgarden	Excursion	Lecture David B. Shmoys
16.00-16.30	Coffee Break	Coffee Break		Coffee Break
16.30-18.30	Exercises Yossi Azar	Exercises Tim Roughgarden		Exercises David B. Shmoys
Evening	Reception			School Dinner

Yossi Azar: Coordination Mechanism and Search Problems

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 on-line algorithms.

Finally, we switch gears and discuss questions related to ordering problems motivated by search problems. In particular we discuss min-sum set cover and its generalizations.

Tim Roughgarden: Approximation Guarantees in Algorithmic Game Theory

We survey two uses of approximation measures in the emerging field of algorithmic game theory: quantifying the inefficiency of game-theoretic equilibria, and designing robust auctions for revenue-maximization. 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.

David B. Shmoys: Approximation Algorithms for Stochastic Optimization Problems

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 2-stage 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, primal-dual 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 LP-rounding, including a stochastic variant of the set covering problem and the closely related uncapacitated facility location problem; for primal-dual results, we will focus on the problem of scheduling the maximum-weight set of on-time jobs; and for random sampling techniques, we will focus on the a priori traveling salesman problem. Furthermore, since an LP-rounding procedure requires solving the linear relaxation first, we will also discuss techniques for solving these exponentially-large 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.

Talks by members of the MPII Department of Algorithms and Complexity

Kurt Mehlhorn: Geometric Computing — The Science of Making Geometric Algorithms Work
Frank Neumann: Bio-inspired Computing
Konstantinos Panagiotou: Random Structures in Computer Science
Pascal Schweitzer: Graph isomorphism, Feedback Vertex Sets and Fixed Parameter Tractability
Julian Mestre: Robust Scheduling