Matchings, Critical Nodes, and Popular Solutions
Matchings, Critical Nodes, and Popular Solutions
复制标题
匹配、关键节点和流行解决方案
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
T. Kavitha
中科院分区：
文献类型：
--
作者：
T. Kavitha
我们考虑了婚姻实例中的一个匹配问题。每个节点都有严格的偏好顺序对其邻居进行排名。有一个优先或关键节点的集合，我们只对那些匹配尽可能多的关键节点的匹配感兴趣。这样的匹配在多个应用程序中很有用，我们称它们为关键匹配。稳定的匹配不必至关重要。我们认为稳定的稳定放松被称为受欢迎。我们的目标是找到一个受欢迎的关键匹配，即在节点是选民的关键匹配中，一个薄弱的condorcet获胜者。我们表明，可以有效地计算流行的临界匹配，而这种匹配始终存在。
We consider a matching problem in a marriage instance G . Every node has a strict preference order ranking its neighbors. There is a set C of prioritized or critical nodes and we are interested in only those matchings that match as many critical nodes as possible. Such matchings are useful in several applications and we call them critical matchings . A stable matching need not be critical. We consider a well-studied relaxation of stability called popularity . Our goal is to find a popular critical matching, i.e., a weak Condorcet winner within the set of critical matchings where nodes are voters. We show that popular critical matchings always exist in G and min-size/max-size such matchings can be efficiently computed.