Admin-Kommentar

Speichern Löschen Gespeichert

Stammdaten

Relaxations for some NP-hard problems based on exact subgraphs
Beschreibung:

Die Klassifizierung von kombinatorischen Optimierungsproblemen in polynomial lösbare und NP-schwere Probleme führt auf die Frage wie man mit letzterer Klasse umgehen sollte.

Es gibt eine allgemeine Übereinstimmung in der wissenschaftlichen Gemeinschaft, dass NP-schwere Probleme nicht polynomial lösbar sind, aber dies ist nicht bewiesen. Die Klärung dieses Sachverhaltes rangiert als eines der Milleniumprobleme in der Clay Sammlung offener mathematischer Probleme.

Nachdem in den 1970iger Jahren die „Computational Complexity“ in der theoretischen Informatik als Maß für die „Schwierigkeit“ von Entscheidungsproblemen eingeführt wurde, gab es große Anstrengungen, um mit NP-schweren Problemen umzugehen. Dieser Zugang geht von einem „worst case“ Verhalten aus, und lässt unmittelbar keine Aussagen über den Lösungsaufwand eines einzelnen Problems zu. Aber selbst wenn ein Problem als nicht polynomial lösbar angenommen wird, ist es immer noch eine mathematische Herausforderung, solche Probleme mit polynomialen Methoden möglichst gut zu approximieren.

Es ist Zweck dieses Projekts, mathematische Methoden zu entwickeln, um einige prominente Klassen von Graphenoptimierungsproblemen möglichst genau zu approximieren. Speziell liegt der Fokus auf Max-Cut, Max-Clique und Graph Coloring.

Der innovative Aspekt des Projekts liegt in der Art und Weise, wie eine Hierarchie von immer genaueren Approximationen aufgebaut wird. Die Idee ist, zu verlangen, dass alle k-elementigen Untergraphen in der konvexen Hülle der zulässigen Lösungen liegen. Je größer der Parameter k gewählt wird, umso genauer wird die Approximation sein. Aus praktischer Sicht wird man mit kleinen Werten von k anfangen, sodass die Projektionsbedingungen noch praktisch durchführbar sind.

Die Herausforderungen liegen in der Identifikation von Untergraphen, deren Projektion die Relaxation verschärfen würde (Separierungsproblem). Es ist geplant sowohl problem-spezifisch als auch allgemein überkopositive Matrizen zu separieren.

Aus algorithmischer Sicht stellt sich die Frage, wie die Projektionsbedingungen am effizientesten behandelt werden können. Hier ist geplant, die Projektionsbedingungen zu dualisieren und die duale Funktion mittels der „Bundle-Methode“ zu optimieren.

Schließlich werden die neuen Approximationen in bestehende exakte Methoden für Max-Cut integriert, um auch größere Probleme noch mittels Branch-and-Bound exakt lösen zu können.

Schlagworte: semidefinite Optimierung, Approximationshierarchien, numerische Behandlung NP-schwerer Probleme
Kurztitel: Relax
Zeitraum: 01.11.2015 - 30.04.2020
Kontakt-Email: -
Homepage: -

MitarbeiterInnen

MitarbeiterInnen Funktion Zeitraum
Franz Rendl (intern)
  • Projektleiter/in
  • 01.11.2015 - 30.04.2020

Kategorisierung

Projekttyp Forschungsförderung (auf Antrag oder Ausschreibung)
Förderungstyp §26
Forschungstyp
  • Angewandte Forschung
Sachgebiete
  • 101016 - Optimierung
Forschungscluster Kein Forschungscluster ausgewählt
Genderrelevanz Genderrelevanz nicht ausgewählt
Projektfokus
  • Science to Science (Qualitätsindikator: I)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Finanzierung

Förderprogramm
Einzelprojekt
Organisation: Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Kooperationen

Keine Kooperationspartner ausgewählt