Thursday, June 20
1:30-3:30 PM
Room 301

Random Methods

The focus of this minisymposium is on random dynamic greedy algorithms. The best examples are packing problems: to find a packing of disjoint objects, order randomly all possible objects and then consider them sequentially, adding each to the packing if possible. The difficulty in analysis comes from the iteration - the probability of accepting y depends on whether previous x had been accepted which in turn depend on previous w, etc. Using reasonable heuristics, differential equations can often be given to model the behavior but as the algorithm continues the randomness may build up and it is difficult to prove that the equations remain almost surely valid. The speakers will discuss recent work on those random methods.

Organizer: Joel H. Spencer
Courant Institute of Mathematical Sciences,
New York University

1:30 Asymptotically Optimal Covering Designs
Daniel M. Gordon, Center for Communications Research, San Diego; Greg Kuperberg, Yale University; Oren Patashnik, Center for Communications Research, San Diego; and Joel H. Spencer, Organizer
2:00 Analysis of Random Algorithms by Differential Equations
Nicholas C. Wormald, University of Melbourne, Australia
2:30 Nearly Perfect Matchings in Regular Simple Hypergraphs
Noga Alon and Jeong Han Kim, AT&T Bell Laboratories; and Joel H. Spencer, Organizer
3:00 Random Greedy Packing
David Grable, Humboldt University, Germany

Registration | Hotel Information | Dormitory Information | Transportation | Speaker Index

MEM, 4/10/96