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.