Sex-Equal Stable Matchings: Complexity and Exact Algorithms
Sex-Equal Stable Matchings: Complexity and Exact Algorithms
复制标题
性别平等稳定匹配：复杂性和精确算法
DOI：
10.1007/s00453-012-9672-0
复制
发表时间：
2014
期刊：
影响因子：
1.1
通讯作者：
Robert W. Irving
中科院分区：
文献类型：
--
作者：
Eric McDermid;Robert W. Irving
我们探索了经典稳定婚姻问题的一种变体的复杂性和精确计算，在该问题中，我们寻求不仅稳定，而且在形式意义上“公平”的匹配。特别是，我们研究了性别平等稳定婚姻问题（SESM），其中，粗略地说，我们希望找到一个稳定的匹配，其性质是男性的幸福感尽可能接近女性的幸福感。众所周知，这个问题是强 NP 难问题（Kato in Jpn. J. Ind. Appl. Math. 10:1–19, 1993）。我们特别考虑 SESM 实例，其中男性和/或女性的偏好列表的长度受常数限制。从消极的一面来看，我们表明 SESM 是 NP 难的，即使男性和女性的偏好列表的长度最多为 3，并且当由解决方案的目标值参数化时，SESM 甚至不属于 XP 类。这强化了 Kato 的 NP 硬度结果（Jpn. J. Ind. Appl. Math. 10:1–19, 1993）。从积极的一面来看，我们通过给出多项式时间算法来证明我们的硬度结果是“紧的”，其中一侧（例如男性）的偏好列表的长度最多为 2，而另一侧（女性）的列表的长度是无界的。此外，我们给出了 SESM 的低阶指数时间算法，其中一侧的偏好列表的长度至多为 l（而另一侧的列表的长度是无界的）。特别是，对于每对常数 $l \in\mathcal{Z}^{+}$ 和 $\epsilon\in\mathcal{R}^{+}$ ，都有一个运行时间以 $O^{\star}(2^{(5 - \sqrt{24})(l-2 + \epsilon)n}) + O^{\star}(2^{\frac {(l-1)}{2\epsilon}})$。因此，如果将 ϵ 选择为足够小的常数，则运行时间为 O⋆(1.0726n)、O⋆(1.1504n)、O⋆(1.2339n)、…，其中 l=3,4,5,… 。
We explore the complexity and exact computation of a variant of the classical stable marriage problem in which we seek matchings that are not only stable, but are also “fair” in a formal sense. In particular, we study the sex-equal stable marriage problem (SESM), in which, roughly speaking, we wish to find a stable matching with the property that the men’s happiness is as close as possible to the women’s happiness. This problem is known to be strongly NP-hard (Kato in Jpn. J. Ind. Appl. Math. 10:1–19, 1993).We specifically consider SESM instances in which the preference lists of the men and/or women are bounded in length by a constant. On the negative side, we show that SESM is NP-hard, even if both the men’s and women’s preference lists are of length at most three, and is not even in the class XP when parameterized by the objective value of the solution. This strengthens the NP-hardness results of Kato (Jpn. J. Ind. Appl. Math. 10:1–19, 1993). On the positive side, we show that our hardness result is “tight” by giving a polynomial-time algorithm for the case in which the preference lists on one side (say the men) are of length at most two, and the lengths of the lists on the other side (the women) are unbounded. Furthermore, we give a low-order exponential-time algorithm for SESM in which the preference lists on one side are of length at most l (and the lengths of the lists on the other side are unbounded). In particular, for every pair of constants $l \in\mathcal{Z}^{+}$ and $\epsilon\in\mathcal{R}^{+}$ there is an algorithm with running time bounded by $O^{\star}(2^{(5 - \sqrt{24})(l-2 + \epsilon)n}) + O^{\star}(2^{\frac {(l-1)}{2\epsilon}})$. Hence, if ϵ is chosen to be a sufficiently small constant, the running time is in O⋆(1.0726n), O⋆(1.1504n), O⋆(1.2339n),… for l=3,4,5,… .