Solutions for the stable roommates problem with payments
Solutions for the stable roommates problem with payments
复制标题
DOI：
10.1016/j.tcs.2013.03.027
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
P. Biró;M. Bomhoff;P. Golovach;W. Kern;D. Paulusma
中科院分区：
文献类型：
--
作者：
P. Biró;M. Bomhoff;P. Golovach;W. Kern;D. Paulusma
带支付的稳定室友问题有一个图G=（V，E）作为输入，其边权重为w：E→ R≥ 0，问题是找到一个稳定的解。一个解是一个匹配M，其向量p∈ R≥ 0 V，对所有的u v∈ M满足pu + pv = w（uv），对所有的u在M中不匹配满足pu = 0。一个解是稳定的，如果它阻止了阻塞对，即相邻顶点对u和v满足p u+ p v< w（u v），或者等价地，如果总阻塞值∑ u v∈ E max {0，w（u v）−（p u+ p v）}= 0。通过精确定位匹配游戏的联盟结构核心的可访问性的关系，我们给出了一个建设性的证明，表明每个是的实例的稳定的室友问题的付款允许一个路径的线性长度，开始在一个任意的不稳定的解决方案，并结束在一个稳定的解决方案。这将Chen，Fujishige和Yang（2011）[4]关于二分实例的结果推广到一般实例。我们还表明，问题的阻塞对和阻塞值，这是找到一个解决方案的最小数量的阻塞对或最小的总阻塞值，分别是NP-困难的。最后，我们证明了第一个问题的变体，其中阻塞对的数量必须最小化相对于一些固定的匹配，是NP-困难的，而这个变体的第二个问题是多项式时间可解的。
The stable roommates problem with payments has as input a graph G=(V, E) with an edge weighting w: E→ R≥ 0 and the problem is to find a stable solution. A solution is a matching M with a vector p∈ R≥ 0 V that satisfies p u+ p v= w (u v) for all u v∈ M and p u= 0 for all u unmatched in M. A solution is stable if it prevents blocking pairs, ie, pairs of adjacent vertices u and v with p u+ p v< w (u v), or equivalently, if the total blocking value∑ u v∈ E max {0, w (u v)−(p u+ p v)}= 0. By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a constructive proof for showing that every yes-instance of the stable roommates problem with payments allows a path of linear length that starts in an arbitrary unstable solution and that ends in a stable solution. This generalizes a result of Chen, Fujishige and Yang (2011)[4] for bipartite instances to general instances. We also show that the problems Blocking Pairs and Blocking Value, which are to find a solution with a minimum number of blocking pairs or a minimum total blocking value, respectively, are NP-hard. Finally, we prove that the variant of the first problem, in which the number of blocking pairs must be minimized with respect to some fixed matching, is NP-hard, whereas this variant of the second problem is polynomial-time solvable.