TITLE:
The Paired Assignment Problem
AUTHORS:
Vardges Melkonian
KEYWORDS:
Matching Problems, Linear Programming, Basic Solutions, Graph Algorithms
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.4 No.2,
April
23,
2014
ABSTRACT: 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.