11. – 16. Mai 2008, Dagstuhl Seminar 08201

Design and Analysis of Randomized and Approximation Algorithms


Martin Dyer (University of Leeds, GB)
Mark R. Jerrum (Queen Mary University of London, GB)
Marek Karpinski (Universität Bonn, DE)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
Dagstuhl's Impact: Dokumente verfügbar


The workshop was concerned with the newest developments in the design and analysis of randomized and approximation algorithms. The main focus of the workshop was on three specific topics: approximation algorithms for optimization problems, approximation algorithms for measurement problems, and decentralized networks as well as various interactions between them. This included all sorts of completely new algorithmic questions that lie on the interface of several different areas. Here, some new broadly applicable techniques have emerged recently for designing efficient approximation algorithms for various optimization and measurement problems. This workshop has addressed the above topics and also some new fundamental paradigms and insights into the algorithm design techniques.

The 30 lectures delivered at this workshop covered a wide body of research in the above areas. The Program of the meeting and Abstracts of all talks are listed in the subsequent sections of this report.

The meeting was held in a very pleasant and stimulating atmosphere. Thanks to everyone who made it a very interesting and enjoyable event.

  • Martin Dyer
  • Mark Jerrum
  • Marek Karpinski

We thank Annette Beyer, Angelika Mueller-von Brochowski and Heike Clemens for their continuous support and help in organizing this workshop.

Dagstuhl Seminar Series


  • Modelling / Simulation
  • Data Structures / Algorithms / Complexity
  • Networks
  • Optimization / Scheduling


  • Randomized Algorithms
  • Approximation Algorithms
  • Optimization Problems
  • Linear and Semidefinite Programming
  • Measurement Problems
  • Decentralized Networks
  • Internet Algorithms
  • Algorithmic Game Theory


Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.