03. – 08. Juni 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)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team


Externe Homepage
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


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.