Design and Analysis of Randomized and Approximation Algorithms

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