« | Dezember 2018 | » | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kontakt
Manuela Bank-Zillmann
Telefon: +49 345 55-21004
Telefax: +49 345 55-27404
presse@uni-halle.de
Universitätsplatz 8/9
06108 Halle
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 |
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.