ETHZ Logo CGC Logo

Fall School on Algorithms for Hard Problems

September 23-27, 2002
Bildungszentrum Matt
Schwarzenberg, Switzerland

Schedule and Abstracts

Sunday, September 22
(late afternoon)
Arrival in Schwarzenberg
Monday, September 23 David Shmoys (Cornell University)
Approximation algorithms for clustering problems: a case study in algorithm design techniques
There has been a great deal of recent progress in research on the design and analysis of approximation algorithms for NP-hard problems, thereby expanding the breadth and depth of techniques used in this area. 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.
Tuesday, September 24 Gerhard Woeginger (University of Twente)
Approximation algorithms for scheduling problems
The least difficult and most benevolent NP-hard problems are probably those that possess a polynomial time approximation scheme (PTAS) or a fully polynomial time approximation scheme (FPTAS). We will discuss some general methods and approaches for deriving such a PTAS/FPTAS. All these methods are based on rounding and enumeration methods, sometimes combined with dynamic programming, or integer programming formulations. We will look at some specific scheduling problems to illustrate these methods in great detail. Moreover, we will discuss some linear programming relaxations that yield approximation algorithms with constant performance guarantee. Finally, we will discuss techniques for disproving the existence of a PTAS or FPTAS (under P/=NP).
Wednesday, September 25
Susanne Albers (Universität Freiburg)
On-line algorithms
Online algorithms have received a lot of research interest during the last 10 to 15 years. In an online problem the input arrives incrementally, one piece at a time. In response to each input portion an algorithm must generate output, not knowing future input. An online algorithm A is c-competitive if, for all inputs, the solution computed by A is at most a factor of c away from the solution computed by an optimal offline algorithm. In this course we first introduce basic concepts and study important results for fundamental online problems such as paging, self organizing lists, the k-server problem and metrical task systems. We then investigate online algorithms in application areas such as robotics, load balancing, financial games and the resource allocation in large networks.
Wednesday, September 25
Excursion (hiking)
Thursday, September 26 Susanne Albers (Universität Freiburg)
On-line algorithms (cont.)
Angelika Steger (Technische Universität München)
Stochastic Scheduling
The NP-completeness of a problem is defined with respect to the worst case analysis of the running time. The drawback of such an analysis is that few or even a single bad instance suffices to get bad bounds. Moreover, worst case examples often require quite intricate constructions and the performance of the given algorithm may be much better on 'typical' instances. Despite the wide acceptance of the worst case analysis there is hence a need for additional models which better capture such behavior. A natural approach is to consider the average case for certain distributions of the problem instances. In the lecture we will cover the state of the art of such 'stochastic' approaches in the area of scheduling theory.
Friday, September 27 Rolf Niedermeier (Universität Tübingen) and Peter Rossmanith (Technische Universität München)
Fixed-Parameter Algorithms
Fixed-parameter algorithms offer a constructive and powerful approach to obtaining practical solutions despite the (almost inevitable) intractability of certain problems. The essential idea is to identify one or more aspects of the input to a problem as the parameters, and to confine the combinatorial explosion of computational difficulty to an additive function of the parameters so that the costs are polynomial in the non-parameterized part of the input.

The canonical example of such a problem is the NP-hard Vertex Cover, where the size k of the cover set is treated as the parameter. For graphs of size n, this problem can be solved in fewer than O(1.29k+kn) time, rendering it useful for values of k less than 200. Such fixed-parameter algorithms have become standard in a variety of application areas such as computational biology, database query evaluation, VLSI, and graph drawing, where small natural parameters are ubiquitous.

Fixed-parameter algorithms are therefore a new tool to solve hard problems exactly. The goals of this course are threefold: To learn the principles of the theory of parameterized complexity (with a glimpse on hardness and completeness), to learn general principles in the design of fixed-parameter algorithms, and to present a number of efficient fixed-parameter algorithms in, among others, graph theory, logic, and computational biology.

Friday, September 27
(after 17:00)

The daily schedule will be roughly as follows:

Breakfast: 7:30 - 9:00
Morning session: 9:00 - 12:00 (lectures and exercises, with a coffee break at 10:00)
Lunch break: 12:00-14:00
Afternoon session: 14:00 - 17:30 (lectures and exercises, with a coffee break at 15:30)
Dinner: 18:00
After-dinner session: 19:30 - 21:00 (discussion of solutions to exercises)

Last modified on 2006-07-23 by Thomas Erlebach      Copyright © 2000-2002 CGC