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
partners


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

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

Peter Allen - London School of Economics and Political Science


A sparse blow-up lemma

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.




Letzte Aktualisierung: 10.06.2013