Multivariate Complexity Analysis of Team Management Problems

In dieser Dissertation identifizieren und entwickeln wir einfache kombinatorische Modelle für vier natürliche Teamverwaltungsaufgaben und untersuchen bezüglich Berechnungskomplexität handhabbare und nicht handhabbare Fälle. Hierzu analysieren wir die multivariate Komplexität der zu Grunde liegenden Probleme und testen manche unserer Algorithmen auf synthetischen und empirischen Daten.

Unsere erste Aufgabe ist es ein Team zu finden, welches von einer Gemeinschaft akzeptiert wird und den Vorstellungen (im Folgenden „Agenda“) eines Chefs entspricht. Wir formalisieren diese Aufgabe mit einem einfachen kombinatorischen Modell, indem wir ein bekanntes Verfahren aus dem Wahlkontext durch ein Agendamodell erweitern. In diesem Modell wird die Gemeinschaft durch Wähler mit je einer „Favoritenmenge“ repräsentiert. Wir zeigen, dass die resultierenden Probleme UNANIMOUSLY ACCEPTED BALLOT und MAJORITYWISE ACCEPTED BALLOT NP-schwer sind, sogar wenn es keine Agenda des Chefs gibt. Hierbei fragt UNANIMOUSLY ACCEPTED BALLOT, ob es ein Team gibt, welches von allen Wählern akzeptiert wird. [–]MAJORITYWISE ACCEPTED BALLOT fragt, ob es ein Team gibt, welches von einer strikten Mehrheit der Wähler akzeptiert wird. Akzeptanz bedeutet in diesem Zusammenhang, dass jeder Wähler die Mehrheit der Teammitglieder unterstützt. Auf der positiven Seite zeigen wir „fixed-parameter tractability“ (FPT) für die Parameter „Anzahl an potentiellen Teammitgliedern“ und „Anzahl an Wählern“. Für den Parameter „maximale Größe der Favoritenmengen“ zeigen wir ein FPT-Ergebnis für UNANIMOUSLY ACCEPTED BALLOT und W[1]-Vollständigkeit für MAJORITYWISE ACCEPTED BALLOT.

Unsere zweite Aufgabe ist es eine Menge von Individuen in homogene Gruppen zu partitionieren. Unter Ausnutzung von Konzepten des kombinatorischen Datenanonymisierungsmodells k-ANONYMITY entwickeln wir ein neues Modell, welches diese Aufgabe formalisiert. Dabei werden die Homogenitätsanforderungen jeder potentiellen Gruppe durch einen „Mustervektor“ spezifiziert. Die Informationen über die Individuen sind in einer Matrix gespeichert, wo Individuen durch Zeilen und ihre Attribute durch Spalten repräsentiert werden. Wir zeigen, dass einige Spezialfälle des sich ergebenden Problems HOMOGENEOUS TEAM FORMATION NP-schwer sind während andere FPT-Ergebnisse ermöglichen. Wir übertragen unser „Mustervektorkonzept“ zurück in die Welt der kombinatorischen Datenanonymisierung und zeigen, dass es helfen kann die Nutzbarkeit der anonymisierten Daten zu verbessern. Wir zeigen, dass das zu Grunde liegende Problem NP-schwer ist und ergänzen dies durch ein FPT-Ergebnis bezüglich eines „Homogenitätsparameters“. Aufbauend darauf entwickeln wir sowohl eine ILP-basierte exakte Lösungsmethode als auch eine Heuristik und testen diese in Experimenten mit empirischen Daten.

Unsere dritte Aufgabe ist es ein Team effektiv auszubilden, um sicherzustellen, dass aus einer Menge von wichtigen Fähigkeiten jede jeweils von der Mehrheit der Teammitglieder beherrscht wird. Wir formalisieren diese Aufgabe durch ein natürliches Matrixmodifikationsproblem auf binären Matrizen, wobei Teammitglieder durch Zeilen und deren Fähigkeiten durch Spalten repräsentiert werden. Das resultierende Problem ist bekannt als LOBBYING im Kontext von Bestechung in Wahlen. Wir untersuchen wie natürliche Parameter wie „Anzahl an Zeilen“, „Anzahl an Spalten“ oder die „maximale Anzahl an fehlenden Einsen pro Spalte um eine Mehrheit an Einsen zu erhalten“ (im Folgenden „Gap-Wert“) die Berechnungskomplexität unseres Problems beeinflussen. Auf der negativen Seite zeigen wir NP-Schwere, sogar wenn jede Zeile höchstens drei Einsen enthält. Auf der positiven Seite zeigen wir zum Beipiel ein FPT-Ergebnis für den Parameter „Anzahl an Spalten“ und entwickeln eine Heuristik mit logarithmischen Approximationsfaktort und testen diese auf empirischen Daten. Als weiteres Schlüsselergebnis zeigen wir, dass unser Problem LOGSNP-vollständig ist für konstante Gap-Werte.

Unsere vierte Aufgabe ist es Teams gleicher Größe neu aufzuteilen. Genauer versucht man die Anzahl gleichgroßer Teams zu reduzieren indem man einige Teams auflöst, deren Mitglieder an nicht in Konflikt stehenden verbleibende Teams verteilt und dabei sicherstellt, dass alle neuen Teams wiederum gleich groß sind. Wir formalisieren diese Aufgabe durch ein neues kombinatorisches Graphmodell. Wir zeigen dessen Beziehungen zu bekannten Graphkonzepten wie Perfekten Matchings, Flussnetzwerken, und Sternpartitionen von Graphen. Auf der negativen Seite zeigen wir, dass das zu Grunde liegende Problem NP-schwer ist, sogar wenn die alte Teamgröße und der Teamgrößenanstieg voneinander verschiedene Konstanten sind. Auf der positiven Seite zeigen wir unter anderem, dass unser Problem in Polynomzeit lösbar ist, wenn es keine Konflikte gibt oder wenn die aufzulösenden und zu gewinnenden Teams bereits bekannt sind.