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, May 21, 2012

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

Lecture - 14:15

Raimund Seidel - Universität des Saarlandes, Saarbrücken

Analyzing String Sorting Algorithms

How expensive is it to quicksort a set $S$ of $n$ strings taking into account that the cost of comparing two strings depends on the length of their common prefix? Clearly $O(n\log n)$ is not the right bound. It is too small. How do you even express a reasonably tight bound? Traditional parameters such as $n$, the number of strings in $S$, and $m$, their cumulative length, are easily seen to be inappropriate. We will show that the \emph{thickness vector,} a parameter set associated with the trie of $S$, allows to express the expected cost of quicksorting $S$ in a very precise manner. The same holds for other sorting methods as well, and even for lower bounds.

Colloquium - 16:00

Nicolai Hähnle - EPFL

The diameter of polyhedra and volume expansion

The well-known Simplex method for linear programming walks along the vertex- edge graph of a polyhedron. How quickly can an optimal vertex be reached in this way? The polynomial Hirsch conjecture claims that there always exists a path whose length is bounded by a polynomial in the number of facets and the dimension (though it makes no claims about how to find such a path!).

We briefly outline some approaches to this problem and then discuss a new upper bound for polyhedra defined by a system of inequalities whose coefficient matrix has bounded subdeterminants. This is joint work with N. Bonifas, M. Di Summa, F. Eisenbrand, and M. Niemeier.

Letzte Aktualisierung: 15.05.2012