Analysis of Algorithms
Krynica Morska (near Gdansk),
|
This is the sixth meeting specifically dedicated to the Average-Case Analysis of Algorithms. The previous ones have been held in Schloss Dagstuhl (Germany) in 1993, 1995, and 1997, in Princeton (USA) in 1998 and in Barcelona (Spain) in 1999 (see Analysis of Algorithms homepage for more information). This year we all meet in Hotel Continental in Krynica Morska, near Gdansk, on the sea shore of Baltic Sea, Poland. The meeting is sponsored by Technical University of Gdansk
Scope . Predicting the performance of algorithms is a likely outgrowth of ongoing research in analytic combinatorics and the analysis of random discrete structures. This workshop will bring together leading researchers in this field to focus on such problems. Probabilistic considerations on inputs and the random combinatorial structures underlying algorithmic analysis have provided an active area of modern research. One assumes some reasonable probability distribution on input instances to an algorithm as a way of understanding the inner workings of the algorithm and its "typical behavior." Experience in the field shows that it is often unwieldy to work with exact models, where on the other hand one can say something meaningful and precise on the typical "asymptotic" behavior of the algorithm, when either the underlying combinatorial structure becomes very large or when the algorithm is challenged by massive data sets. In these cases one sometimes gets simplified but exact expressions dealing with first (or higher) order expansions of averages, moments or distributions, as some parameters of the algorithmic problem grow to be very large. The focus of this workshop is the average case analysis of algorithms, and its relation to the wider areas of analytic combinatorics, exact and limiting distributions, formal techniques, probability theory, combinatorics and computer science. We identify the following areas as being of particular interest:
Atmosphere. Following the tradition of the first four seminars, this seminar intends to bring together leading researchers in the Analysis of Algorithms and provide them with a relaxed atmosphere for interaction and discussion. Therefore, the talks will generally be brief and somewhat sparse. Long lunch breaks and one free afternoon will be purposely planned. A problem session will also be planned.
Special Issue. Following the tradition of previous seminars, we shall organize a special issue of Random Structures & Algorithms to report on the results presented at the seminar.
Program Committee :
Philippe Flajolet, Hosam Mahmoud, Conrado Martinez,
Helmut Prodinger,Robert Sedgewick, and Wojciech Szpankowski (chair).
Organizing Committee: Michal Karonski (co-chair), Marek Kubale, Andrzej Kusiuk (co-chair), Ryszard Sobczak and Jozef Wozniak.
Please download the registration form ( MS document, Postscript), fill it out and send it by fax (+ 48 58 341 61 32) or by ordinary mail to:
Andrzej Kusiuk
Wydzial ETI
Politechnika Gdanska
ul. Narutowicza
80-952 Gdansk
Poland
Hotel Continental
ul. Przyjazni 7
82-210 Krynica Morska.
There are a few other hotels in Krynica Morska that we might use if there is
not enough room in the conference hotel. We expect that most participants will
have single rooms, however, a few might end up in double rooms.