Lanterna Rally

Author: Bredereck, Robert

Publisher: Universitätsverlag der TU Berlin

Published: 2015-08-10

Total Pages: 252

ISBN-13: 3798327645

In this thesis, we identify and develop simple combinatorial models for four natural team management tasks and identify tractable and intractable cases with respect to their computational complexity. To this end, we perform a multivariate complexity analysis of the underlying problems and test some of our algorithms on synthetic and empirical data. Our first task is to find a team that is accepted by competing groups and also satisfies the agenda of some principal. Extending an approval balloting procedure by an agenda model, we formalize this task as a simple combinatorial model where potential team members are represented by a set of proposals and the competing groups are represented by voters with favorite ballots, that is, subsets of proposals. We show that the underlying problems UNANIMOUSLY ACCEPTED BALLOT and MAJORITYWISE ACCEPTED BALLOT are NP-hard even without an agenda for the principal. Herein, UNANIMOUSLY ACCEPTED BALLOT asks for a set of proposals that is accepted by all voters and MAJORITYWISE ACCEPTED BALLOT asks for a set of proposals that is accepted by a strict majority of the voters where acceptance means that each voter supports the majority of the proposals. On the positive side, we show fixed-parameter tractability with respect to the parameters "number of proposals" and "number of voters". With respect to the parameter "maximum size of the favorite ballots" we show fixed-parameter tractability for UNANIMOUSLY ACCEPTED BALLOT and W[1]-completeness for MAJORITYWISE ACCEPTED BALLOT. On the negative side, we show W[2]-hardness for the parameter "size of the solution" and NP-hardness for various special cases. Our second task is to partition a set of individuals into homogeneous groups. Using concepts from the combinatorial data anonymization model k-ANONYMITY, we develop a new model which formalizes this task. The information about the individuals is stored in a matrix where rows represent individuals and columns represent attributes of the individuals. The homogeneity requirement of each potential group is specified by a "pattern vector". We show that some special cases of the underlying problem HOMOGENEOUS TEAM FORMATION are NP-hard while others allow for (fixed-parameter) tractability results. We transfer our "pattern vector" concept back to combinatorial data anonymization and show that it may help to improve the usability of the anonymized data. We show that the underlying problem PATTERN-GUIDED k-ANONYMITY is NP-hard and complement this by a fixed-parameter tractability result based on a "homogeneity parameterization". Building on this, we develop an exact ILP-based solution method as well as a simple but very effective greedy heuristic. Experiments on several real-world datasets show that our heuristic easily matches up to the established "Mondrian" algorithm for k-ANONYMITY in terms of quality of the anonymization and outperforms it in terms of running time. Our third task is to effectively train team members in order to ensure that from a set of important skills each skill is covered by a majority of the team. We formalize this task by a natural binary matrix modification problem where team members are represented by rows and skills are represented by columns. The underlying problem is known as LOBBYING in the context of bribery in voting. We study how natural parameters such as "number of rows", "number of columns", "number of rows to modify", or the "maximum number of ones missing for any column to have a majority of ones" (referred to as "gap value") govern the computational complexity. On the negative side, we show NP-hardness even if each row contains at most three ones. On the positive side, for example, we prove fixed-parameter tractability for the parameter "number of columns" and provide a greedy logarithmic-factor approximation algorithm. We also show empirically that this greedy algorithm performs well on general instances. As a further key result, we prove LOGSNP-completeness for constant gap values. Our fourth task is to redistribute teams of equal size. More precisely, one asks to reduce the number of equal-size teams by dissolving some teams, distributing their team members to non-conflicting non-dissolved teams, and ensuring that all new teams are again of equal size. We formalize this task by a new combinatorial graph model. We show relations to known graph models such as perfect matchings, flow networks, and star partitions. On the negative side, we show that the underlying problem is NP-hard even if the old team size and the team size increase are distinct constants. On the positive side, we show that even our two-party variant of the problem is polynomial-time solvable when there are no conflicts or when the districts to dissolve and the districts to win are known. Furthermore, we show fixed-parameter tractability with respect to treewidth when the old team size and the team size increase are constants. 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.