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, April 21, 2008

Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
room 005

Lecture - 14:15

Remco Veltkamp, Universiteit Utrecht

Properties and Performances of Shape Similarity Measures

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 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

Oliver Klein - FU Berlin

"Biproportional Election Systems and Network Flows"
followed by a short presentation of his thesis
"Matching with Reference Points" (as part of the thesis defense)

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.

Letzte Aktualisierung: 15.04.2008