https://www.dagstuhl.de/05201
15. – 20. Mai 2005, Dagstuhl-Seminar 05201
Design and Analysis of Randomized and Approximation Algorithms
Organisatoren
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
Dokumente
Dagstuhl Seminar Proceedings
Teilnehmerliste
Summary
Most computational tasks today that arise in realistic scenarios are intractable, at least if one insists on exact solutions delivered within a strict deadline. Two important means for surmounting that intractability barmier are randomized and approximate computations. It is an interesting artifact that these two notions of computation 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 three specific topics: approximation algorithms for optimization problems, approximation algorithms for measurement problems, and decentralized networks 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 measurement problems. This workshop has addressed the above topics and also some new fundamental insights into the design techniques.
The 35 lectures delivered at this seminar covered a wide body of research in the above areas. The meeting was hold in a very informal and stimulating atmosphere. Thanks to everyone who made it a very interesting and enjoyable event.
Martin Dyer
Mark Jerrum
Marek Karpinski
Dagstuhl-Seminar Series
- 11241: "Design and Analysis of Randomized and Approximation Algorithms" (2011)
- 08201: "Design and Analysis of Randomized and Approximation Algorithms" (2008)
- 01231: "Design and Analysis of Randomized and Approximation Algorithms" (2001)
- 9124: "Randomized Algorithms" (1991)