Monday, January 5, 2015
Freie Universität Berlin
Institut für Informatik
Takustraße 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
In this talk, I would like to introduce a class of convex polytopes
which appear under different names in different fields of
mathematics. For instance, they go by the name of ``marginal
polytopes'' in statistics, they are called ``partial constraint
satisfaction polytopes'' in combinatorial optimization. They occur as
representation polytopes of abelian permutation groups, and they are
used in tensor decomposition analysis.
In the general setting, a polytope in the family is specified by a
simplicial complex $\Delta$ with vertices labeled by positive
integers.
If all labels are equal to $2$ (binary case), and if $\Delta$ is a
graph, the polytope is a cut polytope.
In spite of their many uses, the facet structure of marginal
polytopes remains mysterious --- particularly so in the non-binary
case.
In joint work with Benjamin Nill and Andreas Paffenholz, we describe a
generalization of the cycle inequalities for cut polytopes to
non-binary labels together with a polynomial time separation
algorithm if the size of the vertex labels is bounded.
Colloquium - 16:00
Abstract:
We give an O(n log n) time algorithm for the exact congruence testing
problem for two sets of n points in 4-space. This problem is to decide if
two point sets in the 4-dimensional Euclidean space are the same up to
rotations and translations. The problem is sensitive to numerical errors,
but since congruence testing with error tolerances is known to be NP-hard,
we restrict our concern to the exact case and use the Real Random-Access
Machine (Real-RAM) model.
For two and three dimensions, there are O(n log n) algorithms due to
Manacher (1976) and Atkinson (1987). It has been conjectured that O(n log
n) algorithms should exist for any fixed dimension. The best algorithm so
far by Brass and Knauer (2000) takes O(n^ceil(d/3) log n) time in
d-dimensional space and therefore O(n^2 log n) in 4-space.