Research Institute for Mathematical Sciences
Kyoto University
Kyoto 606-8502
Japan
Michael Joswig (TU Berlin), 9:00 - 9:45
The tight span of a finite metric space M is polyhedral complex which geometrically describes if and how M deviates from a metric tree. This concept was independently developed by Isbell (1964) and by Bandelt and Dress (1986), and it has been applied successfully to questions of phylogenetics. Later it was observed that the theory of tight spans and their splits allows for a vast generalization to arbitrary convex polytopes (where the finite metric spaces occur as the special case of second hypersimplices). The presentation surveys these results. In addition, we sketch new results concerning matroids and tropical Grassmannians (joint work with Benjamin Schröter).
Simon Hampe (TU Berlin), 10:00 - 10:45
The notion of tropical convexity, i.e. convexity over the min-plus (or max-plus) semiring, has gained significant attention over the last few years, due to applications in various fields. This also made it very desirable to have computational tools for creating and analyzing tropically convex sets. The software system polymake provides just such a set of tools, which I want to exhibit. My talk will begin with a short introduction to tropical convexity in general and its relation to ordinary convexity and tropical algebraic geometry. I will then go over some of the applications, which occur, for example, in optimization, complexity theory and biological statistics. Finally, I will present several features of the new polymake release 3.0. The objects and functions dealing with tropical computations have undergone a complete redesign and I will showcase their new and improved capabilities.
David Bremner (U New Brunswick), 11:00 - 11:45
A fundamental question about two convex bodies is whether they can be separated by a hyperplane. In this talk I will discuss various ways in which degree of seperability or non-seperability can be measured, and the computational complexity of the resulting problems in algorithmic geometry. For the "classical" notion of separability in terms of a widest slab (margin) between the two bodies, there is known dual problem of finding the shortest translation so that the two bodies touch. It turns out there there is a very similar dual for the non-seperable case, namely translating until the two bodies are weakly seperable. We can also measure the degree of (non-)seperability (overlap) by considering the degree to which the two bodies need to be grown (shrunk) before transitioning between separable and non-seperable. I'll discuss the usual scaling operation, the "reduced convex hull" of Bern and Eppstein, and the inner parallel body as candidate methods of shrinking. In addition to various computational complexity issues, I'll try to connect the translation and shrinking points of view.
Skip Jordan (Hokkaido University), 13:30 - 14:15
We describe mplrs, a new parallel vertex/facet enumeration program based on the reverse-search code lrs. The implementation uses MPI and can be used on single machines, clusters and supercomputers. It is a C wrapper that uses the underlying lrs code with few modifications, and was derived from the earlier parallel implementation plrs (written by G. Roumanis). We describe the budgeted parallel tree search implemented in mplrs, an approach that can easily be applied in other applications. We compare with other sequential and parallel programs for vertex/facet enumeration. In some instances, mplrs achieves almost linear scaling with more than 1000 cores. This is joint work with David Avis.