https://www.dagstuhl.de/11241

June 13 – 17 , 2011, Dagstuhl Seminar 11241

Design and Analysis of Randomized and Approximation Algorithms

Organizers

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)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 1, Issue 6 Dagstuhl Report
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

Summary

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.

Acknowledgment

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

Classification

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

Keywords

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

Documentation

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

Publications

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.