Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | preliminary term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, June 17, 2013

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Helmut Alt - Freie Universität Berlin

Stacking and Packing of Geometric Objects

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

Peter Allen - London School of Economics and Political Science

A sparse blow-up lemma

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.

Letzte Aktualisierung: 10.06.2013