Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 5, 2012

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Tibor Szabó - Freie Universität Berlin

Construction and applications of (k,d)-trees

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

José Soto - Technische Universität Berlin

Matroid Secretary Problems: Free Order Model and Laminar Case

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).

Letzte Aktualisierung: 25.10.2012