Relaxations for some NP-hard problems b...

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.