| [home] - [up] |
Abstract: Certain proportional election systems require that the composition of a governing board or parliament is proportional both to the number of votes for each party and, independently, with respect to the size of districts. (Such a system has recently been introduced in the canton of Zurich).
The problem of computing the outcome of an election can be formulated quite directly as a minimum-cost network flow problem with piecewise linear convex costs (building on work of Balinski and Demange as well as Pukelsheim and Gaffke). In fact, the outcome has also a very natural probablilistic interpretation.
The problem is closely related to matrix scaling, where the rows and columns of a positive matrix have to be independently scaled to obtain given row and column sums. Our biproportional election algorithm can be used as an approximation algorithm for this problem, which is faster than previous algorithms.
(Joint work with Martin Zachariasen).
Colloquium - 16:00
Abstract: Helge Tverberg showed in 1966 that any (d+1)(q-1)+1 points in euclidean d-space can be partitioned into q subsets such that their convex hulls have a non-empty intersection.
In my talk, I will discuss the number of Tverberg partitions. New results based on the equivariant method of topological combinatorics will be shown. A combinatorial result on the number of Birch partitions implies a lower bound for the number of Tverberg partitions for arbitrary q.