On Multi-Dimensional Team Formation

TitleOn Multi-Dimensional Team Formation
Publication TypeConference Paper
Year of Publication2019
AuthorsSchibler T, Singh A., Suri S.
Conference NameThe 31st Canadian Conference in Computational Geometry (CCCG)
Date Published08/2019
Conference LocationEdmonton, Canada
Abstract

We consider a team formation problem in multidimensional space where the goal is to group a set of n agents into teams, each of size , to maximize their total performance. The performance of each team is measured by a score, which is the sum of h highest skill values in each dimension. We wish to maximize the sum of team scores. We prove that the problem is NP-hard if the dimension is d = (log n) even for h = 1 and = 4. We then describe an efficient algorithm for solving the problem in two dimensions as well an algorithm for computing a single optimal team in any constant dimension.

Refereed DesignationRefereed