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
partners


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

Abstract:
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