Approximately Stable Matchings with General Constraints
Approximately Stable Matchings with General Constraints
复制标题
DOI：
--
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Yasushi Kawase;Atsushi Iwasaki
中科院分区：
文献类型：
--
作者：
Yasushi Kawase;Atsushi Iwasaki
本文关注的是在一般可行性约束下，将一方（医院或企业）与另一方（医生或工人）进行双边匹配，以使基本目标最大化。在标准模型中，即使可以将多个医生匹配到一家医院，医院也有响应偏好和最大配额。然而，在实际应用中，医院有一些复杂的基本偏好和制约因素。有了这样的偏好（例如，子模）和约束（例如，背包或矩阵相交），稳定的匹配可能不存在。本文首先确定了基于偏好类和约束类的稳定匹配检查和计算的复杂度。其次，我们建立了一个框架来分析这个问题的包装问题，该框架使我们能够访问在线包装算法的丰富，从而我们构建了近似稳定的算法作为广义延迟接受算法的一种变体。我们进一步提供了一些近似结果。
This paper focuses on two-sided matching where one side (a hospital or firm) is matched to the other side (a doctor or worker) so as to maximize a cardinal objective under general feasibility constraints. In a standard model, even though multiple doctors can be matched to a single hospital, a hospital has a responsive preference and a maximum quota. However, in practical applications, a hospital has some complicated cardinal preference and constraints. With such preferences (e.g., submodular) and constraints (e.g., knapsack or matroid intersection), stable matchings may fail to exist. This paper first determines the complexity of checking and computing stable matchings based on preference class and constraint class. Second, we establish a framework to analyze this problem on packing problems and the framework enables us to access the wealth of online packing algorithms so that we construct approximately stable algorithms as a variant of generalized deferred acceptance algorithm. We further provide some inapproximability results.