This is the fourth in an ongoing series of meetings on the analysis of algorithms, which have been held in Dagstuhl, Germany, in the past and are planned for Barcelona and other locations in the future. The 1998 meeting is intended to attract more researchers from the U. S. to the field of analysis of algorithms.
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:
Also, following the tradition of previous seminars, we expect to organize a special issue of Algorithmica to report on the results presented at the seminar.
If you have technical questions about the scientific program, you may contact the main organizer at Hosam Mahmoud: firstname.lastname@example.org Or you may also contact one of the other organizers at: Philippe Flajolet: email@example.com Helmut Prodinger: Helmut.Prodinger@tuwien.ac.at Reobert Sedgewick: firstname.lastname@example.org Wojciech Szpankowski: email@example.com If you have administrative or logistical questions, you may contact Sandy Barbu firstname.lastname@example.org
The following is a list of prospective participants: Baeza-Yates, Ricardo Bergeron, Francois Chen, Jin-Cheng Clement, Julien Coffman, Ed Compton, Kevin Condon, Ann Drmota, Michael Fill, James Flajolet, Philippe Gardy, Daniele Gittenberger, Bernhard Golin, Mordecai Grabner, Peter Hofri, Micha Hwang, Hsien-Kuei Jelekovic, Predrag Knopfmacher, Arnold Lent, Janice Liebehenschel, Jens Louchard, Guy Mahmoud, Hosam Martinez-Parra, Conrado Miller, Victor Nebel, Markus Odlyzko, Andrew Panario, Daniel Panholzer, Alois Pittel, Boris Poblete, Patricio Prodinger, Helmut Reingold, Edward Roura-Ferret, Salvador Rueschendorf, Ludger Schmutz, Eric Sedgewick, Robert Smythe, Robert Soria, Michele Szpankowski, Wojciech Vallee, Brigitte Viola, Alfredo
This workshop is sponsored by DIMACS, in conjunction with the Special Year on Massive Data Sets.