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 11241

Design and Analysis of Randomized and Approximation Algorithms

( Jun 13 – Jun 17, 2011 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:





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.

  • Alexandr Andoni (Microsoft Corp. - Mountain View, US) [dblp]
  • Alexander Barvinok (University of Michigan - Ann Arbor, US) [dblp]
  • Markus Bläser (Universität des Saarlandes, DE) [dblp]
  • Eden Chlamtác (Tel Aviv University, IL)
  • Amin Coja-Oghlan (Goethe-Universität - Frankfurt a. M., DE) [dblp]
  • Colin Cooper (King's College London, GB)
  • Artur Czumaj (University of Warwick - Coventry, GB) [dblp]
  • Martin Dyer (University of Leeds, GB) [dblp]
  • Uriel Feige (Weizmann Institute - Rehovot, IL) [dblp]
  • Alan M. Frieze (Carnegie Mellon University, US) [dblp]
  • Leslie Ann Goldberg (University of Liverpool, GB) [dblp]
  • Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
  • Mathias Hauptmann (Universität Bonn, DE)
  • Thomas Hayes (University of New Mexico - Albuquerque, US) [dblp]
  • Mark R. Jerrum (Queen Mary University of London, GB) [dblp]
  • Michael Kaminski (Technion - Haifa, IL)
  • Ravindran Kannan (Microsoft Research India - Bangalore, IN) [dblp]
  • Marek Karpinski (Universität Bonn, DE) [dblp]
  • Michael Krivelevich (Tel Aviv University, IL) [dblp]
  • Po-Shen Loh (Carnegie Mellon University, US)
  • Tobias Müller (CWI - Amsterdam, NL) [dblp]
  • Alessandro Panconesi (Sapienza University of Rome, IT) [dblp]
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • Lars Praedel (Universität Kiel, DE)
  • R. Ravi (Carnegie Mellon University, US)
  • Heiko Röglin (Universität Bonn, DE) [dblp]
  • Andrzej Rucinski (Adam Mickiewicz University - Poznan, PL)
  • Alex Samorodnitsky (The Hebrew University of Jerusalem, IL)
  • Richard Schmied (Universität Bonn, DE)
  • Christian Sohler (TU Dortmund, DE) [dblp]
  • Gregory B. Sorkin (London School of Economics, GB) [dblp]
  • Leen Stougie (CWI - Amsterdam, NL) [dblp]
  • Ola Svensson (EPFL - Lausanne, CH) [dblp]
  • Edyta Szymanska (Adam Mickiewicz University - Poznan, PL)
  • Claus Viehmann (Universität Bonn, DE)
  • Berthold Vöcking (RWTH Aachen, DE) [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 05201: Design and Analysis of Randomized and Approximation Algorithms (2005-05-15 - 2005-05-20) (Details)
  • Dagstuhl Seminar 08201: Design and Analysis of Randomized and Approximation Algorithms (2008-05-11 - 2008-05-16) (Details)

  • 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