Martin-Luther-Universität Halle-Wittenberg

Kontakt

Manuela Bank-Zillmann

Telefon: +49 345 55-21004
Telefax: +49 345 55-27404

Universitätsplatz 8/9
06108 Halle

Weiteres

Zurück zur Übersicht

Andreas Fischer: Das Minimum Connectivity Inference Problem und Lösungsansätze

Termin Donnerstag, 20. Dezember 2018, 16.15 - 18.00 Uhr
Veranstaltungsart Kolloquium
Einrichtung Naturwissenschaftliche Fakultät II
Veranstalter Institut für Mathematik
Veranstaltungsort Informatikgebäude, Hörsaal 1.04
Straße Von-Seckendorff-Platz 1
PLZ/Ort 06120 Halle (Saale)
Ansprechpartner Prof. Dr. Christiane Tammer
Telefon +49 345-5524673
E-Mail christiane.tammer@mathematik.uni-halle.de

Beschreibung

Das Minimum Connectivity Inference (MCI) Problem ist ein NP-hartes diskretes Optimierungsproblem. Für seine Beschreibung nutzen wir einen vollständigen ungerichteten Graphen. Außerdem ist eine endliche Anzahl von Clustern (Teilmengen der Knotenmenge des Graphen) gegeben.

Die Aufgabe besteht nun darin, eine Kantenmenge E minimaler Kardinalität zu bestimmen, so dass für jedes Cluster diejenigen Kanten aus E, die zwei Knoten des Clusters verbinden, auch den Zusammenhang des Clusters sicherstellen. Die hohe Schwierigkeit des Problems entsteht dadurch, dass sich Cluster überlappen dürfen.

Wir geben einen Überblick über die Forschung zum MCI Problem und zeigen motivierende Beispiele einschließlich Anwendungen. Unser Hauptinteresse gilt Algorithmen zur exakten Lösung des Problems. Dazu betrachten wir die Formulierung des Problems als gemischt-ganzzahlige Optimierungsaufgabe und ihre Lösung. Speziell geben wir eine verbesserte Formulierung an, die es erlaubt, Probleminstanzen moderater Größe zu behandeln. Um die Menge lösbarer Instanzen weiter auszudehnen, befassen wir uns auch mit Reduktionstechniken. Unter geeigneten Voraussetzungen ist es damit etwa möglich, eine gegebene Instanz äquivalent in eine Instanz mit weniger Clustern zu überführen.

Der Referent ist Prof. Andreas Fischer von der Technischen Universität Dresden.

Karte

zurück zur Übersicht

Zum Seitenanfang