Katrin Casel

Wissenschaftliche Mitarbeiterin im DFG-geförderten Forschungsprojekt:

"Parametrisierte Approximation - neue Konzepte und Anwendungen"

Das Projekt betrachtet, wie der Name bereits suggeriert, die Verbindung approximativer Lösungsmethoden mit der parametrisierten Algorithmik zur Bearbeitung komplexitätstheoretisch schwieriger Optimierungs- probleme. "Schwierig" impliziert in diesem Zusammenhang, dass keine effizienten exakten Algorithmen für diese Probleme existieren. 

Approximationsalgorithmen, sprich effiziente Algorithmen, die im allgemeinen keine exakte aber immerhin eine nach gewissen Kriterien gute Lösung berechnen, sind eine der bekanntesten Methoden zur Lösung schwieriger Probleme. Trotz einer Vielfalt von Optimierungsverfahren hat die rein polynomielle Approximation für viele Probleme allerdings strenge Grenzen. Zum Beispiel gibt es unter der Annahme der Unique Games Conjecture keine Approximation mit Güte echt kleiner als k für k-Hitting-Set. Basierend auf der PCP-Darstellung von NP sind in den letzten Jahren immer mehr negative Ergebnisse dieser Art entstanden. Das vergleichsweise jüngere Gebiet der parametrisierten Algorithmen berechnet exakte Lösungen und weicht dagegen in gewisser Weise den Begriff Effizienz auf. Genauer gesagt, wird die Laufzeit der betrachteten Algorithmen nicht nur in Relation zur Problemgröße sondern auch im Bezug auf einen geeigneten Parameter gemessen. Hintergrund dieser Betrachtung ist, dass der gewählte Parameter oft signifikant kleiner ist als die Instanzgröße und ein exponentieller Aufwand in Bezug auf diesen wesentlich geringer ist als allgemeiner exponentieller Aufwand in der Instanzgröße.

Die Idee der parametrisierten Approximation ist die Berechnung besserer approximativer Lösungen durch eine möglichst geringe, durch einen geeigneten Parameter kontrollierbare Verschlechterung der polynomiellen Laufzeit. Mit dieser Art von Algorithmen lassen sich Approximationsgüten auch jenseits unterer/oberer Schranken der rein polynomiellen Approximation erzielen; aber auch für im ursprünglichen Sinne nicht effizient parametrisierbare Probleme ergeben sich mit dem Verzicht auf Exaktheit sinnvolle Parametrisierungen. Allgemein erlaubt dieser Lösungsansatz einen flexibleren Kompromiss zwischen Effizienz und Genauigkeit. Ziel dieser Betrachtung ist die Entwicklung geeigneter abstrakter Modelle und zugehöriger effizienter Lösungsmethoden für Probleme, die sich mit polynomiellen Verfahren nur schlecht approximieren und nur mit hohem Aufwand exakt lösen lassen.

 

Konkret beschäftien wir uns in diesem Zusammenhang mit speziellen Arten von Clustering-Problemen. Konzeptuelle Problemmodellierung und erste Lösungsansätze finden sich (bald) in den Proceedings des International Symposium on Algorithms and Computation (ISAAC 2016):

Building Clusters with Lower-bounded Sizes. (Faisal Abu-Khzam, Cristina Bazgan,  Katrin Casel, Henning Fernau)