Matchings with Lower Quotas: Algorithms and Complexity
Matchings with Lower Quotas: Algorithms and Complexity
复制标题
较低配额的匹配：算法和复杂性
DOI：
10.1007/s00453-016-0252-6
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
Arulselvan A
中科院分区：
文献类型：
--
作者：
Arulselvan A
研究了最大权值多对一匹配问题的自然推广。我们给出了一个无向二部图，在边inE上有权值，在顶点inP上有上下限指标。我们寻求一个最大权值的多对一匹配，满足两组约束：顶点inare最多关联到一个匹配边，而顶点inPare要么不匹配，要么关联到它们的上下配额之间的多个匹配边。这个问题，我们称之为最大权重多对一匹配与上下级配额（WMLQ），适用于大学课程中分配学生到项目的问题，其中必须分配给每个项目的最小和最大学生人数有限制。本文从经典多项式时间算法、固定参数可跟踪性和逼近性等方面对WMLQ的复杂性进行了全面分析。我们在程度和配额约束方面划分了难处理和多项式可处理实例之间的界限，并提供了求解可处理实例的有效算法。我们进一步证明，对于树宽有界的实例，问题可以在多项式时间内解决；然而，相应的运行时间在树宽上是指数的，并且我们证明了这种依赖是必要的，除非。本文还讨论了WMLQ的逼近性：我们给出了一种具有性能保证的一般情况下的逼近算法，它是渐近最佳可能的，除非。最后，我们详细说明了我们的大多数积极结果如何延续到具有较低配额的任意图中的匹配。
We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graphwith weights on the edges inE, and with lower and upper quotas on the vertices inP. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices inAare incident to at most one matching edge, while vertices inPare either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quotaas basis, and we prove that this dependence is necessary unless. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee, which is asymptotically best possible unless. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.
登录
查看更多内容
约束匹配的稳定性和策略验证性：日本医疗匹配中的一个问题及其解决方案
DOI：
10.1257/aer.102.3.366
发表时间：
2012
期刊：
The American Economic Review
影响因子：
--
作者：
Yuichiro Kamada;F. Kojima
通讯作者：
F. Kojima
影响因子：
1.1
作者：
Alimonti, P;Kann, V
通讯作者：
Kann, V
影响因子：
--
作者：
D. Manlove;Gregg O'Malley
通讯作者：
Gregg O'Malley
与法定人数匹配
影响因子：
2
作者：
Daniel Monte;Norovsambuu Tumennasan
通讯作者：
Norovsambuu Tumennasan
最大加权匹配策略及其在对称不定系统中的应用
影响因子：
2.1
作者：
S. Röllin;O. Schenk
通讯作者：
O. Schenk