Dagstuhl-Seminar 11241
Design and Analysis of Randomized and Approximation Algorithms
( 13. Jun – 17. Jun, 2011 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/11241
Organisatoren
- 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)
Kontakt
- Annette Beyer (für administrative Fragen)
Programm
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.
- 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]
Verwandte Seminare
- 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)
Klassifikation
- data structures / algorithms / complexity
- modelling / simulation
- networks
- optimization / scheduling
- www / web
Schlagworte
- Randomized Algorithms
- Approximation Algorithms
- Probabilistically Checkable Proofs
- Approximation Hardness
- Derandomization Techniques
- Optimization Problems
- Integration Problems
- Decentralized Networks
- Internet Algorithms
