Research And Implementation Of Participation Constrained Team Formation Problem

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. The CLUSTERHIRE problem extending this work focuses on finding a profit-maximizing team the total cost of which dose not exceed a given budget. In the problem, experts can be assigned to an arbitrary number of projects which are not required to be all completed. However, experts may overwork in such a scheme of task assignment and in most application scenarios all the projects are supposed to be completed.In this work, we propose a new hire problem which handles the above two concerns. Given a set of projects P with required skills, and a pool of experts X, 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 participationconstrained experts T ? X 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 approximate algorithms behave differently when distinct facets of the problem are involved.