MPII Home PageMPII Home PageMPII Home Page
ALCOM-FT Home Page
Other Conferences Homepage ADFOCS 2001

Feedback & Pictures


MPI Informatik -> Conferences -> ADFOCS 2001 -> Program


The lectures are scheduled in eight blocks of four hours each. Each block starts with 1 1/2 hours of lecture, followed by 1 3/4 hours of exercises + rest, followed by 3/4 hours discussion of exercises. During the exercise periods, the respective lecturer will be around, as well as some fruit, snacks, and drinks.

Thursday, there will be a talk show \Omega(1) reasons to become a computer scientist, starting 11.00 in the morning (will take about an hour). In the afternoon, there will be an excursion to the the old iron and steel works of Völklingen, declared World Cultural Heritage by the UNESCO in 1994; the bus leaves at 14.30 in front of the institute.


September 4
September 5
September 6
September 7
September 8
9.00-13.00 Welzl
Linear Programs
Linear Programs
Talk Show Shmoys
13.00-14.30 Lunch
14.30-18.30 Miltersen
Excursion Maggs
Evening School


Below you find short abstracts of the lectures together with an indication of useful prerequisites. Clicking on the photos gets you to the respective lecturers' homepage.

Emo Welzl

ETH Zürich

Randomized and
combinatorial methods
for LP related problems

to Emo Welzl's homepage

Abstract: There is an ongoing attempt of designing a provably fast method for solving Linear Progams and related optimization problems by combinatorial methods in the unit cost model (as opposed to the bit-model, where polynomial methods are known). Among others, this research has brought forth randomized methods with subexponential running time, but also a number of interesting combinatorial models like Abstract Objective Functions (AOF), Unimodal Numberings, LP-type Problems, Abstract Optimization Problems (AOP), Unique Sink Orientations of Cubes (USO), et cetera. Although many of these models are quite general, so far there has been little success in showing good lower bounds even in these generalized abstractions. As for the simplex method, there are a number of open questions concerning several pivoting rules, notably randomized ones. We shall focus on these aspects and their open ends, and not address other important topics like interior point methods and issues of implementing the simplex method efficiently.

Prerequisites: Some knowledge about algorithms and randomization. Although we will briefly introduce the basics about Linear Programming, some a priori familiarity with the problem will facilitate the entry into the more technical matters.

David Shmoys

Cornell University

Approximation algorithms
for clustering problems:
a case study in
algorithm design techniques

to David Shmoys' homepage

Abstract: There has been a great deal of recent progress in research on the design and analysis of approximation algorithms for NP-hard problems. The breadth and depth of techniques used in this area have made significant advances. We shall examine several different algorithmic paradigms, including LP rounding, primal-dual methods, local search procedures, as well as variants of more traditional greedy-type heuristics, and discuss how these methods can all yield approximation algorithms with specific (worst-case) performance guarantees. We shall focus primarily on just two (closely related) discrete optimization problems, the k-median problem and the uncapacitated facility location problem, and through recent results in this problem domain, we shall illustrate the gamut of the algorithmic techniques listed above.

Prerequisites: Basic algorithms and some knowledge of basic properties of linear programming (should be no issue after Emo's lectures:).

Peter Bro Miltersen

University of Aarhus

Universal methods
for derandomization

to Peter Bro Miltersen's homepage

Abstract: In these lectures, we consider the following questions: 1) How can we amplify the success probability of a randomized algorithm without using too many extra random bits? 2) How can we run a randomized algorithm using an imperfect random source? 3) How can we turn our randomized algorithm into a deterministic one? One can consider these questions both for specific randomized algorithms (using details of the analysis of the algorithms) and for arbitrary ones (i.e., without making assumption about the way the algorithms use the randomness). We shall deal with the latter kind of universal methods for derandomization. In the past few years, significant progress has been made in finding optimal universal methods. We give an introduction to the field, with an emphasis on the role of coding theory in the modern constructions.

Prerequisites: Basic knowledge about randomized algorithms, as is usually obtained in an algorithms class (e.g., Motwani and Raghavan: Randomized algorithms, Cambridge University Press, 1995). Basic knowledge about error correcting codes is useful but not strictly necessary.

Bruce Maggs

Carnegie Mellon University
& Akamai Technologies

Network problems
in theory and practice

to Bruce Maggs' homepage

Abstract: In my lectures we will study Internet content delivery networks (CDNs). We'll look at all aspects CDNs: what they do, how they are engineered, the theory behind them, their limitations, security issues, and the economics of bandwidth consumption on the Internet.

Prerequisites: I'll assume that students have used the Internet. Some background in networking would be helpful, but I'll try to make the lectures self-contained.


Concept, web pages, and local organization by Berthold Vöcking and Hannah Bast. Help with local arrangements: Petra Mayer and Roxane Wetzel. For comments or questions send an email to Partially supported by the Information Society Technologies Programme of the EU under contract number IST-1999-14186 (project ALCOM-FT).

ADFOCS 2001 organized by Hannah Bast & Berthold Vöcking; WWW page last updated on Monday, 03 September 2001.