摘要 Abstract
医院-居民模型用于模拟诸如学校选择、本科学生分配到学位课程等诸多重要问题。在此模型中,为项目分配固定的配额以限制可被指派的代理数量。受所有代理必须匹配的情景启发,我们提出并研究了一种广义容量规划问题,该问题允许在配额方面进行成本可控的灵活性。我们的设定是对医院-居民问题的扩展,其中项目具有常规配额以及相应的成本,表明超出初始配额匹配代理的成本。我们旨在计算一种能够匹配所有代理且基于偏好最优,并最小化局部或全局成本目标的匹配方案。我们证明了存在显著差异——最小化局部目标可以在多项式时间内解决,而最小化全局目标则是NP难的。从积极的角度来看,我们在一般情况和特定困难情况下分别提出了全局目标的近似算法。我们通过基于线性规划的算法实现了特殊困难情况下的近似保证。我们通过展示与算法结果相匹配的下界进一步强化了NP难性。
The Hospital Residents setting models important problems like school choice, assignment of undergraduate students to degree programs, among many others. In this setting, fixed quotas are associated with the programs that limit the number of agents that can be assigned to them. Motivated by scenarios where all agents must be matched, we propose and study a generalized capacity planning problem, which allows cost-controlled flexibility with respect to quotas. Our setting is an extension of the Hospital Resident setting where programs have the usual quota as well as an associated cost, indicating the cost of matching an agent beyond the initial quotas. We seek to compute a matching that matches all agents and is optimal with respect to preferences, and minimizes either a local or a global objective on cost. We show that there is a sharp contrast -- minimizing the local objective is polynomial-time solvable, whereas minimizing the global objective is NP-hard. On the positive side, we present approximation algorithms for the global objective in the general case and a particular hard case. We achieve the approximation guarantee for the special hard case via a linear programming based algorithm. We strengthen the NP-hardness by showing a matching lower bound to our algorithmic result.