The Paired Assignment Problem

• 作者: Vardges Melkonian
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: MATCHING PROBLEMS Linear PROGRAMMING Basic SOLUTIONS GRAPH ALGORITHMS
• 年，卷（期）: 2014,（2）
• 页码范围: 44-54
• 页数: 11页
• 分类号: O1

摘要

We consider a variation of the maximum bipartite matching problem where each completed task must have at least two agents assigned to it. We give an integer programming formulation for the problem, and prove that the basic solutions of LP-relaxation are half-integral. It is shown that a fractional basic solution can be further processed to obtain an optimal solution to the problem.