Program

Emo Welzl

Randomized and
combinatorial methods
for LP related problems

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

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

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

Universal methods
for derandomization

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

Network problems
in theory and practice

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.