Parameterized Approximation - new concepts and new applications
Final Report Abstract
Sowohl approximative als auch parameterisierte Algorithmen bieten Möglichkeiten, die vielmals feststellbare inhärente kombinatorische Komplexität von praktisch relevanten Problemen (zumeist formalisiert durch den Begriff der NP-Schwere) in den Griff zu bekommen. Jeder Anwendungsbereich bietet hier seine eigenen Herausforderungen, aber auch eigene Lösungsansätze. Im Zuge dieses Projektes wurden eingangs verschiedene kombinatorische Ansätze untersucht, die Privatheit von öffentlich zur Verfügung gestellten Daten gewährleisten sollen und die auf der Idee fußen, dass sich der Einzelne stets in einer Menge von Gleichartigen verstecken kann (hiding in the crowd). Wenn nun der Öffentlichkeit nur aggregierte (zusammengefasste) Daten zur weiteren Analyse zur Verfügung gestellt werden, so soll gewährleistet werden, dass einzelne Personen nicht identifiziert werden können. Andererseits sollen die Daten nicht soweit zusammengefasst oder auch verfälscht werden, dass weitere wissenschaftliche Analysen an ihnen wertlos werden. Privatheit und Nutzbarkeit von Daten stehen daher in einem gewissen Widerspruch zueinander. Diese Grundidee bringt zahlreiche Modellierungsfragen mit sich, z.B.: Was bedeutet es, dass Daten gleichartig sind? Wie kann man evtl. gleichartige Daten zusammenfassen? Wie sollten gleichartige Daten repräsentiert werden? In welcher Weise kann man solche aggregierten Daten veröffentlichen? Wie kann man den Nutzen solcher veröffentlicherter Daten sicherstellen? In gewissem Gegensatz zur Literatur, in der zumeist sehr spezielle Szenarien untersucht wurden, stand im Fokus dieses Projektes, einen möglichst allgemeinen Ansatz zur Modellierung zu wählen und dann systematisch Aspekte zu untersuchen, die die algorithmischen Fragen einfacher machen könnten. Dies hat dann schließlich dazu geführt, Approximation und Paramterisierung in Kombination zu betrachten. Der erwähnte allgemeinere Modellierungsansatz brachte auch den Vorteil mit sich, kombinatorische Probleme mitzuerfassen, die üblicherweise nicht im Zusammenhang mit Privatheit diskutiert werden. Darüber hinaus hat diese Sichtweise auch dazu geführt, einige für Spezialfälle veröffentlichte Algorithmen nicht nur auf weitere Fälle zu erweitern, sondern auch grundlegend zu verbessern.
