9th Max-Planck Advanced Course on the Foundations of Computer Science
August 18 - August 22, 2008
Saarbrücken, Germany

Program

There will be eight blocks of lectures, exercises and discussions, two per lecturer. Each block is about 4 hours. A morning or afternoon block will start with 1 1/2 hours of lecture, followed by 1 1/2 hours of exercises (in small groups) with coffee breaks, followed by a 1 hour discussion of the exercises. During the exercise periods, the respective lecturer will be around, as well as some fruits, snacks, and drinks.

There will be two additional slots for talks given by members of the Algorithms and Complexity Group (D1) at MPI.

All lectures will take place in room HS001 ('Hoersaal 1') at the ground floor of the Computer Science builiding (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

August 18
Monday

August 19
Tuesday

August 20
Wednesday

August 21
Thursday

August 22
Friday

9.00-13.00

Anupam Gupta
Metric embeddings and tree approximations

Stefano Leonardi
Cost-sharing methods in approximation algorithms

Stefano Leonardi
Cost-sharing methods for stochastic optimization

D1-talks

Seffi Naor
Introduction to competitive analysis and online primal-dual framework

Seffi Naor
Maximizing revenue from adauctions,
Weighted paging

13.00-14.30

Lunch

14.30-18.30

Stefano Leonardi
Cross-monotonic cost-sharing mechanisms for network design

Excursion

Anupam Gupta
Embeddings into geometric spaces

Anupam Gupta
The dimension of metric spaces
Seffi Naor
General framework: covering and packing and online graph optimization problems

Evening

School Dinner

Lecture(r)s

Below you find short abstracts of the lectures. Clicking on the photos gets you to the respective lecturer's homepage.

Anupam Gupta
Carnegie Mellon University
Metric Techniques in Approximation Algorithms

Abstract.
Handout 1.
Lecture 1.
Exercise 1.
Hints for Exercise 1.
Lecture 2.
Exercise 2.
Lecture 3.

Stefano Leonardi
Sapienza University of Rome
Applications of Cost-Sharing Methods to Hard Optimization Problems

Abstract.
Lecture 1.
Exercise 1.
Lecture 2.
Exercise 2.
Lecture 3.

Seffi Naor
Technion
Primal-dual Algorithms for Online Optimization

Abstract.

Lecture 1.
Exercise 1.
Lecture 2.
Exercise 2.
Lecture 3.

D1-talks

Wednesday 20.08.2008

11:00-11:25 Kurt Mehlhorn

Certifying Algorithms (Abstract)

11:25-11:50 Julian Mestre

Popular Matchings (Abstract)

11:50-12:15 Tobias Friedrich

Quasirandom Rumor Spreading (Abstract)

12:15-12:40 Spyros Angelopoulos

Paging and List Update under Bijective Analysis (Abstract)

12:40-13:05 Hubert Chan

An SDP Primal-Dual Algorithm for Approximating the Lovasz-Theta Function (Abstract)

Organization

ADFOCS 2008 is organized by Khaled Elbassioni &Kurt Mehlhorn. Help with local arrangements: Christina Fries. For comments or questions send an email to adfocs08[at]mpi[minus]inf[dot]mpg[dot]de.

ADFOCS 2008 organized by Khaled Elbassioni &Kurt Mehlhorn. WWW page last updated on Tuesday, 19 August 2008.

Imprint-Dataprotection

Anupam Gupta Carnegie Mellon University		Metric Techniques in Approximation Algorithms Abstract. Handout 1. Lecture 1. Exercise 1. Hints for Exercise 1. Lecture 2. Exercise 2. Lecture 3.
Stefano Leonardi Sapienza University of Rome		Applications of Cost-Sharing Methods to Hard Optimization Problems Abstract. Lecture 1. Exercise 1. Lecture 2. Exercise 2. Lecture 3.
Seffi Naor Technion		Primal-dual Algorithms for Online Optimization Abstract. Lecture 1. Exercise 1. Lecture 2. Exercise 2. Lecture 3.