Monday, May 21, 2012
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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.