Thursday, June 20
1:30-3:30 PM
Room 301
MS14
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
MEM, 4/10/96