论文标题
在多对多环境中流行的关键匹配
Popular Critical Matchings in the Many-to-Many Setting
论文作者
论文摘要
在存在双面偏好和双面较低配额的情况下，我们考虑了多到许多二分的匹配问题。我们问题的输入是二分图G =（a u b，e），其中u b中的每个顶点指定对其邻居的严格偏好顺序。每个顶点都有一个上限和一个较低的配额，表示可以从其附近分配给其的最大和最小顶点。在非正式的两侧较低配额的多一部分设置中，至关重要的匹配是一种匹配，可以在最大可能的范围内实现顶点较低的配额。这是对一对一设置中临界匹配的定义的自然概括[Kavitha T.，FSTTCS 2021]。我们在给定问题中的目标是在一组关键匹配中找到一个流行的匹配。如果与该组合中的任何匹配，则在给定的一组比赛中，匹配在给定的比赛中很受欢迎。在这里，顶点投票在一对比赛之间。我们表明，始终存在的匹配中，它在一组关键匹配中很受欢迎。我们提出了一种有效的算法来计算最大尺寸的这种匹配。我们使用双重证书证明了匹配的普及。
We consider the many-to-many bipartite matching problem in the presence of two-sided preferences and two-sided lower quotas. The input to our problem is a bipartite graph G=(A U B, E), where each vertex in A U B specifies a strict preference ordering over its neighbors. Each vertex has an upper quota and a lower quota denoting the maximum and minimum number of vertices that can be assigned to it from its neighborhood. In the many-to-many setting with two-sided lower quotas, informally, a critical matching is a matching which fulfils vertex lower quotas to the maximum possible extent. This is a natural generalization of the definition of critical matching in the one-to-one setting [Kavitha T., FSTTCS 2021]. Our goal in the given problem is to find a popular matching in the set of critical matchings. A matching is popular in a given set of matchings if it remains undefeated in a head-to-head election with any matching in that set. Here, vertices cast votes between pairs of matchings. We show that there always exists a matching that is popular in the set of critical matchings. We present an efficient algorithm to compute such a matching of the largest size. We prove the popularity of our matching using a dual certificate.
