May 15 – 20 , 2005, Dagstuhl Seminar 05201

Design and Analysis of Randomized and Approximation Algorithms


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

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants


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

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.