Approximation Algorithms for Effective Team Formatio

This dissertation investigates the problem of creating multiple disjoint teams of maximum efficacy from a fixed set of workers. We identify three parameters which directly correlate to the team effectiveness -- team expertise, team cohesion and team size -- and propose efficient algorithms for optimizing each in various settings. We show that under standard assumptions the problems we explore are not optimally solvable in polynomial time, and thus we focus on developing efficient algorithms with guaranteed worst case approximation bounds. First, we investigate maximizing team expertise in a setting where each worker has different expertise for each job and each job may be completed only by teams of certain sizes. Second, we consider the problem of maximizing team cohesion when the set of workers form a social network with known pairwise compatibility. Third, we explore the problem from a game theoretic perspective in which multiple teams compete on a fixed number of workers and the true needs of each team are private. We present allocation algorithms that both incentivize teams to state their needs accurately and allocate workers effectively. Finally, we experimentally measure the correlation between team cohesiveness, team expertise and team efficacy on a social network graph of computer science research co-authorship.