From - Mon Mar 3 22:37:24 1997
Path: Radon.Stanford.EDU!news.Stanford.EDU!su-news-hub1.bbnplanet.com!news.bbnplanet.com!newsxfer3.itd.umich.edu!newsxfer.itd.umich.edu!uunet!in2.uu.net!128.6.21.17!dziuxsolim.rutgers.edu!usenet
From: Barbara Quigley
Newsgroups: comp.theory
Subject: DIMACS Focus on Discrete Probability Workshop on Probabilistic Analysis of Algorithms, May 11-14, 1997
Date: Fri, 28 Feb 1997 11:11:04 -0500
Organization: Rutgers University
Lines: 64
Distribution: inet
Message-ID: <33170398.28C@dimacs.rutgers.edu>
NNTP-Posting-Host: iyar.rutgers.edu
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii; name="Analysis-text"
Content-Transfer-Encoding: 7bit
X-poster: bquigley@dimacs
X-Mailer: Mozilla 3.0 (X11; I; SunOS 5.5 sun4m)
CC: bquigley
Content-Disposition: inline; filename="Analysis-text"
--------------------------------------------------------------------------
| DIMACS: Center for Discrete Mathematics & Theoretical Computer Science |
| A National Science Foundation Science and Technology Center |
--------------------------------------------------------------------------
DIMACS 1996-97 Focus on Discrete Probabililty
DIMACS Workshop on Probabilistic Analysis of Algorithms
Organizers: Alan Frieze and Michael Molloy
EMAIL: af1p+@andrew.cmu.edu, molloy@cs.toronto.edu
May 11-14, 1997
Princeton University
Theme:
Problems arising in the mathematical analysis of algorithms have provided
an important stimulus for the growth in interest in Discrete Mathematics.
Probabilistic techniques have an important role in this endeavour. The
theory of algorithms has undergone an extraordinarily vigorous development
over the last 20 years or so, and probability theory has emerged as one of
its most vital partners. By its nature probabilistic analysis cuts across
the boundaries of Computer Science, Discrete Mathematics, Operations Research
and Probability Theory.
This workshop focusses on the analysis of algorithms in the {\em average
case}, assuming a probabilistic distribution on input instances. The goal is
to obtain good estimates of various performance measures of algorithms such
as solution quality and running time. The main objective is to explain why
many simple algorithms, often used in practice, perform much better than as
predicted by worst-case analysis. Pathological cases are generally rare and
simple algorithms can often be shown to perform well in the average case.
This is especially true in the case of NP-complete problems where it seems
that the probabilistic approach may be the best way and indeed may be the
only way to understand the success of heuristic combinatorial algorithms.
We identify five major sub-areas as the focus of the workshop.
1. Algorithmic Theory of Random Graphs and Related Combinatorial Problems.
2. Analysis of Euclidean Functionals.
3. Linear Programming and Integer Programming Problems.
4. Analysis of Fundamental Algorithms.
5. Average Case Completeness
The workshop will bring together leading researchers in the Analysis of
Algorithms along with younger researchers in the area. There should be about
15-20 lectures presenting progress, trends and open problems together with
ample time for discussion. We believe that bringing together researchers from
these different but closely related areas will result in an interesting
cross-fertilisation of ideas.
The Special Year program is made possible by long term funding from the
National Science Foundation, the New Jersey Commission on Science and
Technology and DIMACS university and industry partners.
DIMACS Center; Rutgers University; P.O. Box 1179; Piscataway, NJ 08855-1179
TEL: 908-445-5928 FAX: 908-445-5932 ** EMAIL: center@dimacs.rutgers.edu
WWW: http://dimacs.rutgers.edu ** TELNET: telnet info.rutgers.edu 90
DIMACS is a partnership of Rutgers University, Princeton University,
AT&T Labs, Bellcore, and Bell Laboratories.