June 3 – 8 , 2001, Dagstuhl Seminar 01231

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


External Homepage
List of Participants
Dagstuhl-Seminar-Report 309


Most computational task that arise in realistic scenarios are intractable, at least if one insists on exact solutions delivered with certainty within a strict deadline. Nevertheless, practical necessity dictates that acceptable solutions of some kind must be found in a reasonable time. Two important means for surmounting the intractability barrier are randomized computation , where the answer is optimal with high probability but not with certainty, or approximate computation , where the answer is guaranteed to be within, say, small percentage of optimality. More often than not, these two notions go hand-in-hand.

The seminar will be concerned with these phenomena. It will address the newest development in the design and analysis of randomized approximation algorithms, and the new fundamental insights into computational approximate feasibility, optimality, and the intractability of various computational problems. The main focus of the workshop is to be on two specific topics and the various interactions between them. The specific topics are the following:

  • Approximation algorithms for optimization problems.
  • Randomization and de-randomizing techniques play a major role here, both in positive (upper bounds) and negative (lower bounds) results. It features for example in the "rounding" step of approximation algorithms based on linear or semidefinite programming relaxations; it is also at the heart of the theory of probabilistically checkable proofs (PCPs) that is the basis for the recent non-approximability results. A number of very significant new results were obtained here recently.
  • Approximation algorithms for measurement problems.
  • The word "measurement" here is used to distinguish a class of problems-determining the cardinality of combinatorially or computationally defined sets, volume, expectation of random variables on configurations of complex systems, etc. - which are very different in flavor of the optimization problems. This theme is less developed than the previous one, but significant progress is currently being made, both in design of efficient approximation algorithms, and in proving the first approximation lower bounds based on the PCP-techniques mentioned before. It is aimed here at investigating further fundamental and intrinsic connections between the efficiency of approximating optimization problems and the efficiency of approximating measurement problems.

The main goal of the seminar is to bring together researchers working in the area of approximation algorithms and approximation complexity of computational problems, and focus on the newest developments (including practical implementations) within, and also in between the above main themes.

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).

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.


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