Monday, April 21, 2008
Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
room 005
Lecture - 14:15
Abstract:
I will give an overview of shape dissimilarity measure properties, such
as metric and
robustness properties, and discuss retrieval performance measures.
A number of shape similarity measures are shortly described and
compared. Since an
objective comparison of their qualities seems to be impossible,
experimental
comparison is needed. The Motion Picture Expert Group (MPEG), a working
group of
ISO/IEC
(see http://www.chiariglione.org/mpeg/) has defined the MPGE-7
standard
for description and search of audio and visual content. A region based and a
contour based shape similarity method are part of the standard. The data
set
created by the MPEG-7 committee for evaluation of shape similarity
measures offers
an excellent possibility for objective experimental comparison of the
existing
approaches evaluated based on the retrieval rate. Their retrieval
results on the
MPEG-7 Core Experiment CE-Shape-1 test set as reported in the literature
and obtained
by a reimplementation are compared and discussed. To compare the
performance of
similarity measures, we built the framework SIDESTEP – Shape-based Image
Delivery
Statistics Evaluation Project.
Colloquium - 16:00
Abstract:
Elections are one of the most basic properties in democracy.
In this talk we will show how the seats of a parliament may be assigned to the party
members in biproportional election systems.
This can be done via integer matrix scaling.
Given a nonnegative matrix A=(a_{ij}), general matrix scaling is the problem of finding positive multipliers lambda_i and \mu_j for the rows and columns of A, such that the resulting matrix (a_{ij}*lambda_i*mu_j) has prespecified row and column sums r_i and s_j, respectively. Furthermore, in the integer matrix scaling problem, the resulting values a_{ij}*lambda_i*mu_j are rounded by a given rounding function.
In this talk we see how Rote and Zachariasen obtain a new algorithm to solve the integer matrix scaling problem in O(n^4 log n) time. They exploit a nice connection between a recent optimization formulation by Gaffke and Pukelsheim, and network flows. Their approach uses standard techniques on a minimum-cost flow problem with convex piecewise linear costs to obtain the desired algorithm.
The illustrated method can be used to obtain an algorithm with runtime O(n^4 (log n + log h/epsilon)) for the general matrix scaling problem, where h is the total sum of all result matrix entries. This improves the previously best known strongly polynomial result by Linial et al. with runtime O(n^7 log h/epsilon) significantly.
The talk is mainly based on the papers "Divisor Methods for Proportional Representation Systems: An Optimization Approach To Vector and Matrix Apportionment problems" by Gaffke and Pukelsheim, and "Matrix Scaling by Network Flow" by Rote and Zachariasen.