Skip to main content
eScholarship
Open Access Publications from the University of California

Multidimensional Team Formation

  • Author(s): Schibler, Thomas
  • Advisor(s): Suri, Subhash
  • et al.
Abstract

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.

Main Content
Current View