Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society University of Saarland

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

ADFOCS 2009



News & Events