We consider the problem of assigning agents to programs in the presence of two-sided preferences, commonly known as the Hospital Residents problem. In the standard setting each program has a rigid upper-quota which cannot be violated. Motivated by applications where quotas are governed by resource availability, we propose and study the problem of computing optimal matchings with cost-controlled quotas -- denoted as the CCQ setting. In the CCQ setting we have a cost associated with every program which denotes the cost of matching a single agent to the program. Our goal is to compute a matching that matches all agents, respects the preference lists of agents and programs and is optimal with respect to the cost criteria. We consider envy-freeness as a notion of optimality and study two optimization problems with respect to the costs -- minimize the total cost (MINSUM) and minimize the maximum cost at a program (MINMAX). We show that there is a sharp contrast in the complexity status of these two problems -- MINMAX is polynomial time solvable whereas MINSUM is NP-hard and hard to approximate within a constant factor unless P = NP even under severe restrictions. On the positive side, we present approximation algorithms for the MINSUM for the general case and a special hard case. We chieve the approximation guarantee for the special case via a technically involved linear programming (LP) based algorithm. We remark that our LP is for the general case of the problem.
翻译:我们考虑在双面偏好的情况下向方案分配代理商的问题,通常称为医院居民问题。在标准设定中,每个方案都有严格的上限,不能违反。我们受配额受资源可用情况制约的申请的驱使,提出并研究与成本控制配额最佳匹配的最佳计算问题 -- -- 称为CCQ设置。在CCQ设置中,我们每个方案的成本都与这两个问题的复杂性形成鲜明对比 -- -- MIMPAX是难以解决的时间问题,而MINSUM是一个与所有代理商匹配的匹配,尊重代理商和方案的优惠名单,并且对成本标准来说是最佳的。我们把无嫉妒视为一个最佳概念,研究与成本有关的两个优化问题 -- -- 最大限度地降低总成本(MINSUM)和在方案(MIMAX)上的最大成本。我们发现,这两个问题的复杂性是截然不同的 -- -- MIMAX是难以解决的时间问题,而MINSUM是坚固的,并且很难在一个不变的因素中估计,除非P=PPPS,我们通过一个非常严格的卡来保证我们这个特殊的常规的SL。