Monday, May 14, 2012
Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
room 005
Lecture - 14:15
Abstract:
Given a finite list of convex bodies in Euclidean space, a packing is a union of nonoverlapping congruent copies of the bodies given. A natural question concerning packings is how dense they can be made, that is, what is the maximum fraction of space that can be covered by a packing of some given bodies?
I wil show how harmonic analysis and semidefinite programming can be used to give upper bounds for the maximum density of a packing of bodies. In particular I will discuss the case of binary sphere packings, when one considers packings of spheres of two different sizes, and show how the computer can be used to find upper bounds for the densities of such packings.
This is joint work with David de Laat and Frank Vallentin.
Colloquium - 16:00
Abstract:
The well-known notion of stable matchings can be extended in several interesting directions, one of them deals with dynamic network flows. In this problem, edges have transit times and a time horizon is given as well, moreover, vertices have preference lists on their adjacent edges. In this talk, we will show how stable flows over time can model real-world market situations. As a proof of existence, we will present a variant of the Gale-Shapley algorithm that computes a stable dynamic flow in pseudo-polynomial time, investigate the case with infinite time horizon and study the influence of storage at vertices.
This is a joint work with Jannik Matuschke and Martin Skutella.