Graduiertenkolleg: Methods for Discrete Structures

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

Monday Lecture and Colloquium

Monday, January 28, 2013

Technische Universität Berlin
Institut für Mathematik
10623 Berlin
room MA 041

Lecture - 14:15

Piotr Faliszewski - AGH University of Science and Technology, Krakow

How difficult is it to elect a parliament

There are many ways in which a society can elect a parliament to govern in its stead. However, many of these methods have various flaws. Some choose parliaments that do not represent the members of the society proportionally, some focus too much on voters' top preferences, and some... have too high computational complexity to use in practice! In this talk we will survey some recent progress on the hardness of winner determination for these difficult parliament-electing rules (such as Monroe's rule and Chamberlin--Courant's rule). We will also introduce and discuss some of their axiomatic properties.

Colloquium - 16:00

Torsten Ueckerdt - Karlsruhe Institute of Technology

Packing Polyominoes Clumsily

We investigate the most unefficient way to pack polyominoes (generalized dominoes) in the plane in such a way that no further polyomino can be added. In particular, for a set D of polyominoes, a packing of the plane with D is a maximal set of copies of polyominoes from D that are not overlapping. A packing with smallest density is called a clumsy packing. In this talk, we answer the question whether clumsy packings are always periodic, whether a clumsy packing (or at least its density) can be computed efficiently and what is the clumsiest among all polyominoes of a given size.

Motivated by their beautiful and charming puzzle character, such problems have always been a fascinating task occupying the minds of mathematicians, computer scientists, chemists and many others. However, the clumsy polyomino problem also serves as a special case of the fundamental minimum maximal independent set problem in graphs.

This is joint work with Maria Axenovich and Stefan Walzer from Karlsruhe Institute of Technology.

Letzte Aktualisierung: 11.10.2013