Dissertations, Theses, and Capstone Projects
Date of Degree
9-2017
Document Type
Dissertation
Degree Name
Ph.D.
Program
Computer Science
Advisor
Amotz Bar Noy
Committee Members
Matthew P. Johnson
Saad Mneimneh
David Peleg
Subject Categories
Theory and Algorithms
Keywords
approximation algorithms, graph theory, combinatorial optimization, game theory, team formation
Abstract
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 pri- vate. 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.
Recommended Citation
Rabanca, George, "Approximation Algorithms for Effective Team Formation" (2017). CUNY Academic Works.
https://academicworks.cuny.edu/gc_etds/2353