August 18 – 22 , 1997, Dagstuhl Seminar 9734

Combinatorial Approximation Algorithms


Y. Rabani (Haifa), D. B. Shmoys (Cornell), G. Woeginger (TU Vienna)

For support, please contact

Dagstuhl Service Team


Aims & Scope
Dagstuhl's Impact: Documents available
Dagstuhl-Seminar-Report 187


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.


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

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.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.