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.