Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
This thesis studies online selection problems, with a particular focus on designing constant-competitive algorithms that require less prior information than existing ones. In particular, we present two such algorithms: one for a variant of the matroid secretary problem and the other in the online contention resolution context. The first setting considered in this thesis is based on the matroid secretary problem (MSP). In MSP, elements of a weighted matroid are revealed one by one and the goal is to pick some of them, so that the selection forms an independent set of as large weight as possible. This setting is motivated by applications in online mechanism design and generalizes the classical secretary problem. It was conjectured that, similar to the classical secretary, there exists an algorithm that is constant-competitive for any matroid constraint. Despite the long line of work dedicated to the problem, so far constant competitive ratio has been attained only for certain classes of matroids and for some variations of MSP. One example is the random assignment model (RAMSP), where an adversary fixes a number of weights equal to the ground set size of the matroid, which then get assigned randomly to the elements of the ground set. However, the two known constant-competitive algorithms for this setting, one by Soto (2013) and the other by Oveis Gharan and Vondrák (2013), crucially rely on knowing the full matroid upfront. Lifting this requirement was left as an open question by the aforementioned authors, as there are good arguments for why such assumptions on prior information should be avoided. In this thesis, we present a constant-competitive algorithm for RAMSP that only needs to know the cardinality of the underlying matroid upfront, making RAMSP the first known MSP variant admitting such an algorithm. The second part of the thesis is concerned with random order online contention resolution schemes (ROCRS), which are structured online rounding algorithms with numerous applications and links to other ...