Invited Session Mon.1.H 3005

Monday, 10:30 - 12:00 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]



Chair: Lionel Pournin



Monday, 10:30 - 10:55 h, Room: H 3005, Talk 1

Lionel Pournin
The flip-graph of the 4-dimensional cube is connected


Flip-graph connectedness is established for the vertex set of the 4-dimensional cube. This result makes it possible to completely enumerate the triangulations of this vertex set in a reasonable time: it is found that there are 92487256 such triangulations, partitioned into 247451 symmetry classes.



Monday, 11:00 - 11:25 h, Room: H 3005, Talk 2

Felix Schmiedl
Gromov-Hausdorff distance of finite metric spaces


The Gromov-Hausdorff distance of two compact metric spaces is a measure for how far the two spaces are from being isometric. It is a pseudometric on the space of compact metric spaces and has been extensively studied in the field of metric geometry.
In recent years, a lot of attention has been devoted to computational aspects of the Gromov-Hausdorff distance. One of the most active topics is the problem of shape recognition, where the goal is to decide whether two shapes given as polygonal meshes are equivalent under certain invariances.
In this talk, we will investigate the computational complexity of several decision versions of the problem. By relating it to other well known combinatorial optimization problems like the clique and the graph isomorphism problem, we prove that determining the largest subspaces of two finite metric spaces with a fixed upper bound on the Gromov-Hausdorff distance is not in APX. Furthermore novel algorithms for the problem will be derived from these results.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.