Cost-minimizing team hires with participation constraint

Team formation, which aims to form a team to complete a given task by covering its required skills, furnishes a natural way to help organizers complete projects effectively. In this work, we propose a new team hiring problem. Given a set of projects [Formula: see text] with required skills, and a pool of experts [Formula: see text], each of which has his own skillset, compensation demand and participation constraint (i.e., the maximum number of projects the expert can participate in simultaneously), we seek to hire a team of participation-constrained experts [Formula: see text] to complete all the projects so that the overall compensation is minimized. We refer to this as the participation constrained team hire problem. To the best of our knowledge, this is the first work to investigate the problem. We also study a special case of the problem, where the number of projects is within the participation constraint of each expert and design an exact algorithm for it. Since participation constrained team hire problem is proven to be NP-hard, we design three novel efficient approximate algorithms as its solution, each of which focuses on a particular perspective of the problem. We perform extensive experimental studies, on both synthetic and real datasets, to evaluate the performance of our algorithms. Experimental results show that our exact algorithm far surpasses the brute-force solutions and works well in practice. Besides, the three algorithms behave differently when distinct facets of the problem are involved.