Lectures and Colloquia during the semester

Freie Universität Berlin - Institut für Informatik

Takustraße 9

14195 Berlin

Room 005 - map -

*Abstract:*
Max-plus algebra was established by M. Plus (1990) after having found
applications in shortest path computations, scheduling theory, dynamical
systems, formal languages, communication complexity and other branches of
mathematics. Max-plus algebra is a variation of matrix algebra where
max and + replace the usual operations + and x. Many properties of
the +/x algebra over the "usual" ring of reals carry over to max-plus
algebra; some of them hold in a modified context. For example, there is an
extensive theory of linear equations and eigenvalue s. I will briefly survey
some of these results and applications.
Then I will consider in more detail the rank of a matrix A, which can be
defined as the smallest number of rank-1 matrices whose sum is A. In the
context of max-plus algebra, a matrix has rank 1 if it can be written as a
*sum matrix (a_{ij})=(u_i+v_j)_{i,j}*, for two vectors u and v. So the
max-plus rank of A is the smallest number of sum matrices whose elementwise
maximum is A.
Barvinok (1996) showed that, for any fixed k, the (maximum) traveling
salesman problem can be approximated in polynomial time if the cost matrix
is the negative of a cost matrix with max-plus rank at most k. Barvinok,
Johnson, and Woeginger (1998) strengthened this result: They showed
that one can even compute the optimal longest traveling salesman
tour in polynomial time, if k is fixed.
Such cost matrices occur for example as distance matrices for point sets
in space under a polyhedral norm, where the unit ball of the norm is a
polytope with k facets.

**Colloquium - 16:00**

*Abstract:*
The task of matching two two-dimensional shapes arises naturally in man
applications, e.g. in computer graphics, computer vision and computer aided
design. In this talk I will present the first algorithm for matching two
polygonal curves f and g under translations with respect to the Frechet
distance. As a popular illustration of the Frechet distance suppose a man
is walking his dog, he is walking on the one curve the dog on the other.
Both are allowed to control their speed but are not allowed to go backwards.
The Frechet distance of the curves is the minimal length of a leash that is
necessary. If f and g consist of m and n segments, respectively, the algo-
rithm has running time *O((mn)^{3}(m+n)^{2}log(m+n))*. This result is joint
work with Helmut Alt and Carola Wenk.