Combinatorial Approximation Algorithms

Summary

The Dagstuhl seminar on Combinatorial Approximation Algorithms brought together 54 researchers with affiliations in Austria (1), France (1), Germany (11), Hungary (1), Iceland (1), Israel (7), Italy (1), Netherlands (2), Russia (1), Sweden (1), Switzerland (1), United Kingdom (3), and USA (23). In 35 talks the participants presented their latest results on approximation algorithms, covering a wide range of topics. The abstracts of most of these talks can be found in this report. Moreover, there is a list of open problems that were stated in the open problem session.

Special events were a hiking tour on Wednesday afternoon and an open problems session held on Thursday evening. In the open problem session, Mark Jerrum, Dorrit Hochbaum, David Shmoys, Vijay Vazirani, and David Williamson presented lists with their favorite open problems. Following the example of Paul Erdös, David Williamson offered money rewards for solutions to his open problems; Sanjeev Arora. and Luca Trevisan managed to solve one of his problems (on the Rectilinear Steiner Arborescence problem) by Friday morning.

Due to the outstanding local organization and the pleasant atmosphere, this seminar was a most enjoyable and memorable event.