Monday, November 5, 2012
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
We study the concept of (k,d)-trees introduced by Heidi Gebauer in her PhD-thesis. We show how these trees are related to several seemingly unrelated problems, including ones about satisfiability of Boolean formulas, Maker-Breaker positional games, searching with lies, and tenure games. Our main contribution, which eventually implies all our applications, is the construction of (k,d)-trees with (asymptotically as) small d (as possible).
This represents joint work with Heidi Gebauer and Gabor Tardos.
Colloquium - 16:00
In the (standard) matroid secretary problem we want to incrementally construct an independent set of large weight on a given matroid in which the weights are revealed in random order. A well-known conjecture claims the existence of a constant-factor approximation for this problem for any matroid.
The free order model is a relaxed version of the problem above with the only difference that one can choose the order in which elements reveal their weights. In this talk we will motivate the original problem and present the first constant factor approximation for this relaxed version.
If time permits, we will also discuss the standard matroid secretary problem on laminar matroids and present a constant factor approximation for this problem.
This is joint work with Patrick Jaillet (MIT) and Rico Zenklusen (Johns Hopkins University).