Popular matchings
Popular matchings
复制标题
热门搭配
DOI：
10.1137/06067328x
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
K. Mehlhorn
中科院分区：
文献类型：
--
作者：
David J. Abraham;Robert W. Irving;T. Kavitha;K. Mehlhorn
我们考虑将一组申请人与一组<i>帖子相匹配的问题帖子的子集按偏好顺序，可能涉及领带。申请人的数量偏爱M'</i>而不是M <i> m </i>超过申请人的数量在本文中，我们给出了第一个多项式时间算法，以确定一个实例是否允许流行的匹配，并找到最大的匹配。严格订购的每个优先列表（即没有纽带），我们给出一个<i> o </i>（<i> n </i>+<i> m </i>）时间算法，其中<i > n </i>是申请人和职位的总数，<i> m </i>是所有的总长度首选项列表。最大核电性二手匹配问题。
We consider the problem of matching a set of <i>applicants</i> to a set of <i>posts</i>, where each applicant has a <i>preference list</i>, ranking a non-empty subset of posts in order of preference, possibly involving ties. We say that a matching <i>M</i> is <i>popular</i> if there is no matching <i>M'</i> such that the number of applicants preferring <i>M'</i> to <i>M</i> exceeds the number of applicants preferring <i>M</i> to <i>M'</i>. In this paper, we give the first polynomial-time algorithms to determine if an instance admits a popular matching, and to find a largest such matching, if one exists. For the special case in which every preference list is strictly ordered (i.e. contains no ties), we give an <i>O</i>(<i>n</i>+<i>m</i>) time algorithm, where <i>n</i> is the total number of applicants and posts, and <i>m</i> is the total length of all the preference lists. For the general case in which preference lists may contain ties, we give an <i>O</i>(√<i>nm</i>) time algorithm, and show that the problem has equivalent time complexity to the maximum-cardinality bipartite matching problem.