Date of Degree

9-2017

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor(s)

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.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.