Monday, June 27, 2016
Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
In many problems of extremal combinatorics the uniqueness of the extremal structure aids the proof of optimality. Problems with two or more
extrema often pose a much greater, sometimes insurmountable combinatorial challenge. In certain cases the difficulties posed by multiple
extremal examples can be mitigated by realizing that the combinatorial problem, or rather its extremal structures, hide the features and
concepts of another mathematical discipline in the background. In such cases, the extremal structures can be described more
naturally in another mathematical language.
Ryser's Conjecture states that for every r-partite r-uniform hypergraph it is possible to find a vertex cover of size only (r-1)-times the matching number. For r=2 Ryser's Conjecture reduces to König's Theorem, for r=3 it was proved by Aharoni by topolgical methods, while for larger r it is wide open. In the talk we will be focusing on those hypergraphs that are extremal for Ryser's Conjecture, that is their vertex cover number is exactly (r-1)-times their matching number. An intricate extension of Aharoni's topological method provides a characterization of the 3-uniform Ryser-extremal hypergraphs. In the talk we describe a recent joint work with Ahmad Abu-Khazneh, János Barát, and Alexey Pokrovskiy, where we construct many non-isomorphic Ryser-extremal hypergraphs, for an infinite sequence of uniformities r. These constructions provide further indication that Ryser's Conjecture, if true in general, will not be solved by purely combinatorial methods.
Colloquium - 16:00
Abstract:
Online algorithms are algorithms that have to make decisions before knowing the entire input. In a worst-case analysis, one considers the worst possible input for the algorithm and compares it to the respective best offline solution (competitive ratio). For a number of problems, however, this perspective is too pessimistic because a hypothetical adversary can trick the algorithm. In such cases, it is useful to look at input models with stochastic components. For example, the adversary may still determine the input but not its order. This is drawn at random from all possible permutations.
In this talk, we study linear packing problems in an online setting. The variables of a packing linear program arrive one after the other. We get to know a variable's contributions to objective function and constraints only when it arrives and we have to sets its value immediately and irrevocably. One example of such a problem is online knapsack: Objects of different profits and weights arrive one after the other. We have to choose a subset of these objects so as to maximize the profit while keeping the overall weight below a given bound. In a worst-case analysis, no reasonable performance can be guaranteed. In contrast, with random arrival order, it is possible to get close to the optimal offline solution. We give a simple algorithm achieving the optimal competitive ratio.