Publications

RANK AGGREGATION is important in many areas ranging from web search over databases to bioinformatics. The underlying decision problem KEMENY SCORE is NP-complete even in case of four input rankings to be aggregated into a "median ranking". We study efficient polynomial-time data reduction rules that allow us to find optimal median rankings. On the theoretical side, we improve a result for a "partial problem kernel" from quadratic to linear size. On the practical side, we provide encouraging experimental results with data based on web search and sport competitions, e.g., computing optimal median rankings for real-world instances with more than 100 candidates within milliseconds.

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.