Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 10, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Lutz Warnke
Consider a universe of size $n$ with a family of sets, each of size $k$, such that each element is in ~$D$ sets and any two elements have only $o(D)$ common sets. Asymptotics are for fixed $k$ and with $n, D \to \infty$. A subfamily of ~$n/k$ disjoint sets is called an asymptotic optimal packing. The existence of such a packing was shown by Pippenger and Spencer in 1989.
In this talk I will explain a simpler proof from Spencer which analyzes a random greedy algorithm. It is based on establishing a connection between the algorithm and a Poisson birth process.
Paper by Joel Spencer, Asymptotic Packing via A Branching Process, Random Structures and Algorithms 7 (2) (1995).
Automatic MiSe System Software Version 1.4803M | admin login