Title | On Multi-Dimensional Team Formation |
Publication Type | Conference Paper |
Year of Publication | 2019 |
Authors | Schibler T, Singh A., Suri S. |
Conference Name | The 31st Canadian Conference in Computational Geometry (CCCG) |
Date Published | 08/2019 |
Conference Location | Edmonton, 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 Designation | Refereed |