Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 08201

Design and Analysis of Randomized and Approximation Algorithms

( May 11 – May 16, 2008 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:




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.

  • Dimitris Achlioptas (University of California - Santa Cruz, US) [dblp]
  • Alexander Barvinok (University of Michigan - Ann Arbor, US) [dblp]
  • Piotr Berman (Pennsylvania State University - University Park, US)
  • Markus Bläser (Universität des Saarlandes, DE) [dblp]
  • Magnus Bordewich (Durham University, GB) [dblp]
  • Amin Coja-Oghlan (University of Edinburgh, GB) [dblp]
  • Colin Cooper (King's College London, GB)
  • Mary Cryan (University of Edinburgh, GB)
  • Artur Czumaj (University of Warwick - Coventry, GB) [dblp]
  • Christoph Dürr (Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Martin Dyer (University of Leeds, GB) [dblp]
  • Uriel Feige (Weizmann Institute - Rehovot, IL) [dblp]
  • Alan M. Frieze (Carnegie Mellon University, US) [dblp]
  • Bernd Gärtner (ETH Zürich, CH) [dblp]
  • Leslie Ann Goldberg (University of Liverpool, GB) [dblp]
  • Catherine Greenhill (UNSW - Sydney, AU) [dblp]
  • Peter Gritzmann (TU München, DE)
  • Mathias Hauptmann (Universität Bonn, DE)
  • Thomas Hayes (Toyota Technological Institute - Chicago, US) [dblp]
  • Dorit S. Hochbaum (University of California - Berkeley, US)
  • Markus Jalsenius (University of Liverpool, GB)
  • Mark R. Jerrum (Queen Mary University of London, GB) [dblp]
  • Marek Karpinski (Universität Bonn, DE) [dblp]
  • Michael Langberg (The Open University of Israel - Raanana, IL)
  • Andrzej Lingas (Lund University, SE)
  • Russell Martin (University of Liverpool, GB)
  • Moni Naor (Weizmann Institute - Rehovot, IL) [dblp]
  • Alantha Newman (Rutgers University - New Brunswick, US) [dblp]
  • Kim Thang Nguyen (Ecole Polytechnique - Palaiseau, FR)
  • Konstantinos Panagiotou (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • David Richerby (University of Leeds, GB) [dblp]
  • Richard Schmied (Universität Bonn, DE)
  • Georg Schnitger (Universität Frankfurt, DE)
  • Alexander D. Scott (University of Oxford, GB) [dblp]
  • Christian Sohler (Universität Bonn, DE) [dblp]
  • Leen Stougie (CWI - Amsterdam, NL) [dblp]
  • Ola Svensson (IDSIA - Manno, CH) [dblp]
  • Zoya Svitkina (Dartmouth College - Hanover, US)
  • Claus Viehmann (Universität Bonn, DE)
  • Ingo Wegener (TU Dortmund, DE)

Related Seminars
  • Dagstuhl Seminar 9124: Randomized Algorithms (1991-06-10 - 1991-06-14) (Details)
  • Dagstuhl Seminar 01231: Design and Analysis of Randomized and Approximation Algorithms (2001-06-03 - 2001-06-08) (Details)
  • Dagstuhl Seminar 05201: Design and Analysis of Randomized and Approximation Algorithms (2005-05-15 - 2005-05-20) (Details)
  • Dagstuhl Seminar 11241: Design and Analysis of Randomized and Approximation Algorithms (2011-06-13 - 2011-06-17) (Details)

  • 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