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