UC Santa Barbara

We consider a team formation problem in multi-dimensional space where the goal is to group a set of n agents into a teams, each of size b, 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 = Omega(log n), even for scoring parameter h=1 and team size b = 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.