 |
Universität Augsburg
|
|
|
Universität Augsburg
|
|
M. Sc. Thomas Hirschmüller
Universität Augsburg
spricht am
Dienstag, 21. April 2026
um
15:45 Uhr
im
Raum 1009 (L1)
über das Thema:
| Abstract: |
|
In 1977, Ahlswede and Katona proposed the isoperimetric problem of finding minimum average distance codes (MADCs). These are codes with minimum average (Hamming-) distance among all binary codes of a given size and length. It turns out that every MADC is a so-called discrete ball. Given a center $c \in \mathbb{R}^n$ and a radius $r \in \mathbb{R}$, a discrete ball is defined as
\[
B(c,r) = \{x \in \{0,1\}^n: \left\Vert x-c \right\Vert_1 \leq r\}.
\]
While discrete balls first appeared as optimal solutions of a Coding theory problem, they appear in lots of different areas in Combinatorics. In this talk, I will look at discrete balls through the lenses of Combinatorial optimization and Matroid theory. First, I will show how they are connected to the Knapsack problem. Then, I will talk about how they behave similar to matroids. Finally, combining both results, I will present a new class of Knapsack instances for which it is computationally easy to find an optimal solution. |
| Hierzu ergeht herzliche Einladung. |