Department Kolloquium Sommer 2023
Department, Kolloquium |
Approximation algorithms for packing problems
Andreas Wiese, TUM, 14:30-15:30 Uhr
Packing problems arise in many settings, for example, when loading cargo into a truck or a shop, when assigning virtual servers to real servers, and in general, when limited resources play a role. Packing problems are typically computationally hard; therefore, we do not expect to find efficient algorithms that solve them optimally. Thus, we study approximation algorithms which are efficient algorithms that compute solutions that are provably close to the optimal solution. In this talk, we will see recent results in approximation algorithms for multi-dimensional geometric packing problems and the unsplittable flow on a path problem, an important packing problem that arises in throughput maximization and scheduling.
What are higher algebraic structures and how do they appear in geometry and physics?
Claudia Scheimbauer, TUM, 16:00-17:00 Uhr
Given three rings we can arrange them in a way that any two of the rings can be pulled apart, but altogether we cannot. This arrangement, called the Borromean rings, has been used in many cultures, but to prove this property mathematically is a non-trivial task. This linkedness can be shown by the non-vanishing of the “Massey product” in algebraic topology and exhibits one of the first examples of a “higher structure”. More generally, one of the central concepts in topology is to use loops to study the shape of a space. However, when doing this, a weak form of associativity appears, and certain higher structures precisely capture this behaviour. In the last 2 decades, these ideas have entered algebraic geometry and even number theory, for instance, counting the intersection points of algebraic curves which are not transverse correctly, it is helpful to understand the appearing formulas (which of course are much older) using a version of algebraic geometry built using higher structures; and in turn these techniques led to deep new results, most prominently by Scholze and Lurie.
Higher structures of a related but different nature appear when organizing spacetimes and spaces (modelled by manifolds and manifolds with boundaries) into a structure suitable for characterizing certain (mostly topological) quantum field theories. These so-called higher categories include information about the moduli space of spacetimes (varying the spacetime a bit) and can be used to encode the notion of locality of a field theory. Recent progress has been towards understanding symmetries of quantum field theory.
I will give a (gentle!) introduction to these structures by examples and explain how my own research fits into this picture.