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 05201

Design and Analysis of Randomized and Approximation Algorithms

( May 15 – May 20, 2005 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



Most computational tasks today that arise in realistic scenarios are intractable, at least if one insists on exact solutions delivered within a strict deadline. Two important means for surmounting that intractability barmier are randomized and approximate computations. It is an interesting artifact that these two notions of computation go hand-in-hand.

The seminar 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. 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 insights into the design techniques.

The 35 lectures delivered at this seminar covered a wide body of research in the above areas. The meeting was hold in a very informal and stimulating atmosphere. Thanks to everyone who made it a very interesting and enjoyable event.

Martin Dyer
Mark Jerrum
Marek Karpinski

  • Markus Bläser (ETH Zürich, CH) [dblp]
  • Norbert Blum (Universität Bonn, DE)
  • Magnus Bordewich (University of Leeds, GB) [dblp]
  • Christian Borgs (Microsoft Research - Redmond, US)
  • Moses Charikar (Princeton University, US) [dblp]
  • Jennifer T. Chayes (Microsoft Research - Redmond, US) [dblp]
  • Amin Coja-Oghlan (HU Berlin, DE) [dblp]
  • Mary Cryan (University of Edinburgh, GB)
  • Artur Czumaj (NJIT - Newark, US) [dblp]
  • Martin Dyer (University of Leeds, GB) [dblp]
  • Alan M. Frieze (Carnegie Mellon University, US) [dblp]
  • Olga Gerber (Universität Kiel, DE)
  • Stefanie Gerke (ETH Zürich, CH)
  • Leslie Ann Goldberg (University of Warwick - Coventry, GB) [dblp]
  • Anupam Gupta (Carnegie Mellon University, US) [dblp]
  • Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
  • Mathias Hauptmann (Universität Bonn, DE)
  • Thomas Hayes (University of California - Berkeley, US) [dblp]
  • Kamal Jain (Microsoft Research - Redmond, US) [dblp]
  • Markus Jalsenius (University of Warwick - Coventry, GB)
  • Klaus Jansen (Universität Kiel, DE) [dblp]
  • Mark R. Jerrum (University of Edinburgh, GB) [dblp]
  • Marek Karpinski (Universität Bonn, DE) [dblp]
  • Peter Korteweg (TU Eindhoven, NL)
  • Andrei Krokhin (Durham University, GB) [dblp]
  • Michael Langberg (CalTech - Pasadena, US)
  • Johannes Langguth (Universität Bonn, DE) [dblp]
  • Andrzej Lingas (Lund University, SE)
  • Russell Martin (University of Warwick - Coventry, GB)
  • James B. Matthews (University of Edinburgh, GB)
  • Haiko Müller (University of Leeds, GB) [dblp]
  • Moni Naor (Weizmann Institute - Rehovot, IL) [dblp]
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • Kasper Pedersen (University of Warwick - Coventry, GB)
  • R. Ravi (Carnegie Mellon University, US)
  • Tim Roughgarden (Stanford University, US) [dblp]
  • Miklos Santha (Université Paris Sud, FR) [dblp]
  • Nicolas Schabanel (ENS - Lyon, FR)
  • Gregory B. Sorkin (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
  • Leen Stougie (TU Eindhoven, NL) [dblp]
  • Berthold Vöcking (RWTH Aachen, DE) [dblp]
  • David B. Wilson (Microsoft Research - Redmond, US)
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
  • Uri Zwick (Tel Aviv University, IL) [dblp]

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 08201: Design and Analysis of Randomized and Approximation Algorithms (2008-05-11 - 2008-05-16) (Details)
  • Dagstuhl Seminar 11241: Design and Analysis of Randomized and Approximation Algorithms (2011-06-13 - 2011-06-17) (Details)