Monday, January 28, 2013
Technische Universität Berlin
Institut für Mathematik
room MA 041
Lecture - 14:15
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
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.