The Paired Assignment ProblemReportar como inadecuado

The Paired Assignment Problem - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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


Matching Problems, Linear Programming, Basic Solutions, Graph Algorithms

Cite this paper

Melkonian, V. 2014 The Paired Assignment Problem. Open Journal of Discrete Mathematics, 4, 44-54. doi: 10.4236-ojdm.2014.42007.

Autor: Vardges Melkonian



Documentos relacionados