13. – 17. Juni 2011, Dagstuhl Seminar 11241

Design and Analysis of Randomized and Approximation Algorithms


Martin Dyer (University of Leeds, GB)
Uriel Feige (Weizmann Institute – Rehovot, IL)
Alan M. Frieze (Carnegie Mellon University, US)
Marek Karpinski (Universität Bonn, DE)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 1, Issue 6 Dagstuhl Report
Gemeinsame Dokumente
Programm des Dagstuhl Seminars [pdf]


Many, if not most computational tasks that arise in realistic scenarios are computationally difficult, and no efficient algorithms are known that guarantee an exact (or optimal) solution on every input instance. Nevertheless, practical necessity dictates that acceptable solutions be found in a reasonable time. Two basic means for surmounting the intractability barrier are randomized computation, where the answer is optimal with high probability but not with certainty, and approximate computation, where the answer is guaranteed to be within, say, small percentage of optimality. Often, these two notions 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 the following specific topics: randomized approximation algorithms for optimization problems, approximation algorithms for counting problems, methods for proving approximation hardness, 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 counting problems as well as for proving approximation hardness bounds. This workshop has addressed the above topics and some new fundamental insights and paradigms in this area.

Approximation comes in several flavors as well. For example, in combinatorial optimization problems, the goal of an approximation algorithm is to find a feasible solution whose value is close to optimal. In other cases (such as determining the cardinality of combinatorially or computationally defined sets, volume, expectation of random variables on configurations of complex systems), the goal may be only to estimate some value, rather than exhibit any particular solution. The use of randomness often simplifies the design of approximation algorithms, and is very commonly used for estimation problems.

The 26 regular talks and other presentations 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 hold in a very informal and stimulating atmosphere. Thanks to everyone who made it such an interesting and enjoyable event.


We thank Annette Beyer and Angelika Mueller-von Brochowski for their continuous support and help in organizing this workshop. Thanks go to Mathias Hauptmann for his help in collecting abstracts of the talks and other related materials for these Proceedings.

Dagstuhl Seminar Series


  • Data Structures / Algorithms / Complexity
  • Modelling / Simulation
  • Networks
  • Optimization / Scheduling
  • Www / Web


  • Randomized Algorithms
  • Approximation Algorithms
  • Probabilistically Checkable Proofs
  • Approximation Hardness
  • Derandomization Techniques
  • Optimization Problems
  • Integration Problems
  • Decentralized Networks
  • Internet Algorithms


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.