Monday, June 17, 2013
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
Consider n objects (e.g., simple polygons in the plane) which can be moved either by translations or rigid motions. The objective is to move the objects into a position minimizing
the size (area or perimeter) of a convex container, i.e., the convex hull of their union. The objects may be allowed to overlap ("stacking") or not ("packing"). Already very
specialized variants of the problem turn out to be NP-hard. We will present a survey on exact solutions that have been found for various variants of the problem for
small numbers of objects and approximate solutions for arbitrarily many.
Colloquium - 16:00
Abstract:
The blow-up lemma of Komlós, Sárközy and Szemerédi has been central to many results in extremal graph theory over the last fifteen years. Recently, with Böttcher, Hán, Kohayakawa and Person, we proved versions of the blow-up lemma which work for relatively dense subgraphs of sparse random or pseudorandom graphs. I will explain what a blow-up lemma is, how one might prove it, and what one can do with a sparse blow-up lemma.