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 with required skills, and a pool of experts , 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 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.团队组建（Team Formation）旨在通过覆盖任务所需技能来组建团队以完成指定任务，是帮助组织者高效推进项目的天然解决方案。本研究提出一种全新的团队雇佣问题：给定一批带有既定技能需求的项目与一个专家池，每位专家均拥有自身的技能集合、薪酬诉求与参与约束（即该专家可同时参与的最大项目数量），我们需要雇佣受参与约束限制的专家组建团队以完成全部项目，并使得总薪酬成本最低。我们将该问题定义为带参与约束的团队雇佣问题（Participation Constrained Team Hire Problem）。据我们所知，本研究为首例针对该问题的探索性工作。此外，我们还研究了该问题的一类特殊场景：当项目总数不超过每位专家的参与约束时，并针对该场景设计了精确算法。鉴于带参与约束的团队雇佣问题已被证明为NP难问题，我们设计了三种新颖高效的近似算法作为其求解方案，每种算法分别聚焦于该问题的某一特定维度。我们通过合成数据集与真实数据集开展了大量实验研究，以评估所提算法的性能表现。实验结果表明，我们的精确算法性能远超暴力求解方案，且在实际场景中表现优异。此外，当涉及问题的不同维度时，三种算法的性能表现各有差异。