Emo Welzl
ETH Zürich
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
Cornell University
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
University of Aarhus
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
Carnegie Mellon University
& Akamai Technologies
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.
|