M/911

Ähnlich wie “Orientierte Matroide” als eine Abstraktion derjenigen Matroide angesehen werden können, die über einem angeordneten Körper darstellbar sind, liefern “Bewertete Matroide” einen Rahmen für solche Matroide, die über einem Körper mit einer nichtarchimedischen Bewertung – etwa einer p-adischen Bewertung – darstellbar sind. In dem Vortrag werden wichtige Klassen von Beispielen “Bewerteter Matroide” vorgestellt, bevor aufgezeigt wird, dass gewisse Optimierungsprobleme der “Diskreten Optimierung” genau auf die Bewerteten Matroide zugeschnitten sind. Insbesondere wird eine Variante des klassischen Greedy-Algorithmus präsentiert. Schließlich wird es um die “Optimierung von Paaren unter Abstandsbedingungen” gehen. Das betrifft insbesondere das Problem, zwei aufspannende B¨aume eines zusammenh¨angenden gewichteten Graphen zu konstruieren, die nicht zu viele Kanten gemeinsam haben und – in zu präzisierendem Sinne – jeweils ein möglichst geringes Gesamtgewicht haben. Als praktische Anwendung denke man hier etwa an ein elektrisches Netzwerk, dessen Kanten Kosten verursachen, wobei aber eine gewisse Wahrscheinlichkeit besteht, dass mindestens eine – unbestimmte – Verbindung aufgrund einer Störung ausfällt.

Vortrag zu der Veranstaltung: Masterseminar Kombinatorische Geometrie

PD Dr. Walter Wenzel