Diplomarbeit

Algorithmic and complexity-theoretic studies of combinatorial problems in statistical databases von Katrin Casel

Thema

Allgemeine komplexitätstheoretische Untersuchung abstrakter Modelle zur Anonymisierung von Mikrodaten und Erstellung von Lösungsverfahren basierend auf den Methoden der parametrisierten Komplexität

Zusammenfassung

Betrachtet wird das abstrakte Problem, eine gegebene Boolesche Matrix mit einer Menge von sog. merging-Operationen (Verschmelzungen benachbarter Zeilen/Spalten bezüglich komponentenweise logischem UND) in die Null-Matrix zu überführen. Diese Art der Matrixtransformation ist eine Abstraktion für die Generalisierung von Mikrodaten, die in Kombination mit der Einschränkung auf gerade range-queries ein Verfahren zur 2-Anonymisierung bildet. Das Anwenden einer merging-Operation bedeutet in diesem Kontext einen Informationsverlust, welcher möglichst gering sein sollte. Als Maß bieten sich dabei mehrere Möglichkeiten; hier werden einerseits die Anzahl verwendeter Operationen und andererseits die Anzahl veränderter Zeilen/Spalten motiviert und betrachtet.

Zunächst werden verschiedene eingeschränkte Varianten für die resultierenden Entscheidungsprobleme ("Existiert eine Lösung mit Maß höchstens k?") betrachtet. Diese Untersuchung ergibt einerseits polynomielle Lösungsmethoden für gewisse Subprobleme und weist andererseits NP-Härte bereits für die Einschränkung auf Instanzen mit maximal zwei Eins-Einträgen pro Zeile/Spalten nach. Weiter werden die Probleme als parametrisiert bezüglich der Zielfunktionsgröße (Anzahl Operationen bzw. veränderter Zeilen/Spalten) betrachtet. Dabei werden einige Reduktionsregeln vorgestellt, die eine Reduktion auf einen quadratischen Problemkern ermöglichen. Basierend auf den zuvor erarbeiteten Verfahren für polynomiell lösbare Subprobleme werden außerdem parametrisierte Suchbaumalgorithmen entwickelt.